1、基本介绍

2、应用案例-单旋转（左旋转）

创建出数列{4,3,6,5,7,8}对应的平衡二叉树：

思路分析：
1）创建一个新的节点newNode，值为当前根节点的值
2）将newNode的左子树设置为当前根节点左子树：
  newNode.left=left
3）将newNode的右子树设置为当前根节点右子树的左子树：
  newNode.right=right.left
4）将当前根节点的值换为右子节点的值：
  value=right.value
5）将当前根节点的右子树设置为右子树的右子树：
  right=right.right
5）将当前根节点的左子树设置为newNode：
  left=newNode

代码实现：

    //左旋转方法
    private void leftRotate() {
        //创建新的结点，以当前根结点的值
        Node newNode = new Node(value);
        //把新的结点的左子树设置成当前结点的左子树
        newNode.left = left;
        //把新的结点的右子树设置成带你过去结点的右子树的左子树
        newNode.right = right.left;
        //把当前结点的值替换成右子结点的值
        value = right.value;
        //把当前结点的右子树设置成当前结点右子树的右子树
        right = right.right;
        //把当前结点的左子树(左子结点)设置成新的结点
        left = newNode;
    }

3、应用案例-单旋转（右旋转）

创建出数列{10,12,8,9,7,6}对应的平衡二叉树：

思路分析：
1）创建一个新的节点newNode，值为当前根节点的值
2）将newNode的右子树设置为当前根节点右子树：
  newNode.right=right
3）将newNode的左子树设置为当前根节点左子树的右子树：
  newNode.left=left.right
4）将当前根节点的值换为左子节点的值：
  value=left.value
5）将当前根节点的左子树设置为左子树的左子树：
  left=left.left
5）将当前根节点的右子树设置为newNode：
  right=newNode

代码实现：

    //右旋转方法
    private void rightRotate() {
        Node newNode = new Node(value);
        newNode.right = right;
        newNode.left = left.right;
        value = left.value;
        left = left.left;
        right = newNode;
    }

4、应用案例-双旋转

思路分析：
1）当符合右旋转的条件时
2）如果它的左子树的右子树高度大于它的左子树的高度
3）先对当前节点的左节点进行左旋转
4）再对当前节点进行右旋转即可

代码实现：
改变Node类中的add方法即可。

  // 添加结点的方法
    // 递归的形式添加结点，注意需要满足二叉排序树的要求
    public void add(ANode node) {
        if (node == null) {
            return;
        }

        // 判断传入的结点的值，和当前子树的根结点的值关系
        if (node.value < this.value) {
            // 如果当前结点左子结点为null
            if (this.left == null) {
                this.left = node;
            } else {
                // 递归的向左子树添加
                this.left.add(node);
            }
        } else { // 添加的结点的值大于 当前结点的值
            if (this.right == null) {
                this.right = node;
            } else {
                // 递归的向右子树添加
                this.right.add(node);
            }

        }

        //当添加完一个结点后，如果: (右子树的高度-左子树的高度) > 1 , 左旋转
        if(rightHeight() - leftHeight() > 1) {
            //如果它的右子树的左子树的高度大于它的右子树的右子树的高度
            if(right != null && right.leftHeight() > right.rightHeight()) {
                //先对右子结点进行右旋转
                right.rightRotate();
                //然后在对当前结点进行左旋转
                leftRotate(); //左旋转..
            } else {
                //直接进行左旋转即可
                leftRotate();
            }
            return ; //必须要!!!
        }

        //当添加完一个结点后，如果 (左子树的高度 - 右子树的高度) > 1, 右旋转
        if(leftHeight() - rightHeight() > 1) {
            //如果它的左子树的右子树高度大于它的左子树的高度
            if(left != null && left.rightHeight() > left.leftHeight()) {
                //先对当前结点的左结点(左子树)->左旋转
                left.leftRotate();
                //再对当前结点进行右旋转
                rightRotate();
            } else {
                //直接进行右旋转即可
                rightRotate();
            }
        }
    }

    // 返回左子树的高度
    public int leftHeight() {
        if (left == null) {
            return 0;
        }
        return left.height();
    }

    // 返回右子树的高度
    public int rightHeight() {
        if (right == null) {
            return 0;
        }
        return right.height();
    }

    // 返回 以该结点为根结点的树的高度
    public int height() {
        return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    }

    //左旋转方法
    private void leftRotate() {
        //创建新的结点，以当前根结点的值
        ANode newANode = new ANode(value);
        //把新的结点的左子树设置成当前结点的左子树
        newANode.left = left;
        //把新的结点的右子树设置成带你过去结点的右子树的左子树
        newANode.right = right.left;
        //把当前结点的值替换成右子结点的值
        value = right.value;
        //把当前结点的右子树设置成当前结点右子树的右子树
        right = right.right;
        //把当前结点的左子树(左子结点)设置成新的结点
        left = newANode;
    }

    //右旋转
    private void rightRotate() {
        ANode newANode = new ANode(value);
        newANode.right = right;
        newANode.left = left.right;
        value = left.value;
        left = left.left;
        right = newANode;
    }