平衡二叉树-双旋转

平衡二叉树-双旋转

左右旋转

​ 在某些情况下，单旋转不能完成平衡二叉树的转换

针对于左右型（LRR，LRL）

右左旋转

针对于右左型（RLL，RLR）

代码实现

    //如果右子树高度-左子树高度的值大于1进行左旋转
        if(root.rightHeight()-root.leftHeight()>1){
            //如果当前结点的右子树的左子树高度大于当前结点的右子树的右子树的高度
            // 先对当前结点的右子树进行右旋转
            if (root.getRight().leftHeight()>root.getRight().rightHeight()){
                root.getRight().rightRotate();
            }
            //对当前结点进行左旋转
            root.leftRotate();
            return;
        }
        //如果左子树高度-右子树高度大于1进行右旋转
        if (root.leftHeight()-root.rightHeight()>1){
            //如果当前结点的左子树的右子树高度大于当前结点的左子树的左子树的高度
            //先对当前结点的左子树的进行左旋转
            if (root.getLeft().rightHeight()>root.getLeft().leftHeight()){
                root.getLeft().leftRotate();
            }
            //对当前结点进行右旋转
            root.rightRotate();
            return;
        }