Java数据结构：平衡二叉树（AVL）

一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST)：

发现二叉排序树的问题：

• 左子树全部为空，从形式上看，更像一个单链表.
• 查询速度明显降低(因为需要依次比较), 不能发挥二叉排序树BST的优势，因为每次还需要比较左子树，其查询速度比单链表还慢，解决方案-平衡二叉树(AVL)

一、基本介绍

• 平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树， 可以保证查询效率较高。
• 具有以下特点：它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

二、平衡二叉树（AVL）的实现

这个博客已经讲了二叉排序树（BST）的实现：https://www.jianshu.com/p/32899bd9b69a
而平衡二叉树就是在二叉排序树的基础上增加左旋转和右旋转的方法

• 左旋转的实现：

代码：

   //左旋转方法
private void leftRotate() {
    Node newNode = new Node(this.value); //创建一个新节点
    newNode.left = this.left; //让新节点的左指针指向根节点左子树
    newNode.right = this.right.left; //新节点的右指针指向根节点的右子节点的左子树
    this.value = this.right.value; //把当前节点的值赋为右子节点的值
    this.right = this.right.right; 
    this.left = newNode;        
}

• 右旋转的实现：

代码：

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

当然还要计算节点高度的方法：

      //计算当前节点的高度
public int height() {       
    return Math.max(this.left == null ? 0 : this.left.height(), this.right == null ? 0 : this.right.height()) + 1;
}

//计算左节点的高度
public int leftHeight() {
    if(this.left == null) {
        return 0;
    }else {
    return this.left.height();
    }
}

//计算右节点的高度
public int rightHeight() {
    if(this.right == null) {
        return 0;
    }else {
    return this.right.height();
    }
}

最后在添加方法中加入就行了：

      //添加方法
    public void add(Node node) {
        if(this.value > node.value) {
            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);
            }
        }
        //判断是否需要左右旋转
        if(this.leftHeight() + 1 < this.rightHeight()) {
            if(this.right != null && right.leftHeight() > right.rightHeight()) {
                right.rightRotate();
                this.leftRotate();
            }else {
            this.leftRotate();
            }
        }
        if(this.leftHeight() > this.rightHeight() + 1) {
            if(this.left != null && left.rightHeight() > left.leftHeight()) {
                left.leftRotate();
                this.rightRotate();
            }else {
            this.rightRotate();
            }
        }
    }