AVL树

“No pain, no palm; no thorns, no throne; no gall, no glory; no cross, no crown.”

首先，给出关于平衡因子的定义，它是指树中某结点其左子树的高度和右子树的高度之差。

AVL树是高度平衡的二叉树，它的特点是：AVL树中的任何节点的两个子树的高度最大差别为1。(即平衡因子的绝对值小于2)AVL的优势是在查找时避免了出现一般二叉排序树查找的最坏情况(数据极端情况下, 二叉搜索树会退化成为单链表)。但是AVL在经过插入和删除结点的操作之后可能出现不平衡的情况，所以每次插入或删除完之后要判断是否平衡，不平衡就需要rebalance，这会增加插入删除的复杂度。

AVL树

上面的两张图片，左边的是AVL树，它的任何节点的两个子树的高度差别都<=1；而右边的不是AVL树，因为7的两颗子树的高度相差为2(以2为根节点的树的高度是3，而以8为根节点的树的高度是1)。

AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。如果在AVL树中插入或删除节点后，使得高度之差大于1。此时，AVL树的平衡状态就被破坏，它就不再是一棵二叉树；为了让它重新维持在一个平衡状态，就需要对其进行旋转处理。学AVL树，重点的地方也就是它的旋转算法；在后文的介绍中，再来对它进行详细介绍。

AVL树的Java实现

1. 节点

给出节点定义代码如下：

public class MyAVLTree<T extends Comparable<T>> {

    //根节点
    private AVLTreeNode<T> mRoot;

    //AVL树的节点(内部类)
    class AVLTreeNode<T extends Comparable<T>>{
        T key; //关键字，键值
        int height; //高度
        AVLTreeNode<T> left; //左孩子
        AVLTreeNode<T> right; // 右孩子

        public AVLTreeNode(T key, AVLTreeNode<T> left, AVLTreeNode<T> right) {
            this.key = key;
            this.height = 0;
            this.left = left;
            this.right = right;
        }
    }

    //规定只有一个
    private int height(AVLTreeNode<T> tree){
        if(tree != null){
            return tree.height;
        }
        return 0;
    }

    public int height(){
        return height(mRoot);
    }

    private int max(int a, int b) {
        return a>b ? a : b;
    }
}

MyAVLTree是AVL树对应的类，而AVLTreeNode是AVL树节点，它是AVLTree的内部类。AVLTree包含了AVL树的根节点，AVL树的基本操作也定义在AVL树中。AVLTreeNode包括的几个组成对象:

key: 关键字，是用来对AVL树的节点进行排序的。
left: 左孩子。
right: 右孩子。
height: 高度

2.AVL树不平衡的情况

AVL树大部分操作都和BST树相同, 只有在插入删除结点时, 有可能造成AVL树失去平衡, 而且只有那些在被插入/删除结点到根节点的路径上的结点有可能出现失衡, 因为只有那些结点的子树结构发生了变化。当插入新结点导致不平衡时, 我们需要找到距离新节点最近的不平衡结点为轴来转动AVL树来达到平衡。这种失去平衡的可以概括为4种姿态：LL(左左)，LR(左右)，RR(右右)和RL(右左)。下面给出它们的示意图：

失去平衡姿态

上图中的4棵树都是“失去平衡的AVL树”,从左到右的情况依次是：从左往右的情况依次是：LL、LR、RL、RR。(下面以插入失去平衡为例)

1.左子树的左子树插入节点(左左)

插入或删除一个节点后，根节点的左子树的左子树还有非空子节点，导致“根的左子树的高度”比“根的右子树的高度”大2，导致了AVL树失去了平衡。例如，在上图中，由于根节点(8)的左子树(6)的左子树还有非空节点，而根节点(8)的右子树(9)没有子节点，导致了根节点(8)的左子树(6)高度比根节点(8)的右子树(9)高2，失去平衡。

LL失去平衡的情况，可以通过一次旋转让AVL恢复平衡，如下图：

LL右旋

图中左边是旋转之前的树，右边是旋转之后的树。从中可以发现，旋转之后的树又变成了AVL树，而且该旋转只需要一次即可完成。对于LL旋转，你可以这样理解为：LL旋转是围绕”失去平衡的AVL根节点”进行的，也就是节点k2；而且由于是LL情况，即左左情况，就用手抓着”左孩子，即k1”使劲摇。将k1变成根节点，k2变成k1的右子树，”k1的右子树”变成”k2的左子树”。

给出LL的旋转代码如下:

    /**
     * LL：左左对应的情况(左单旋转)。
     */
    public AVLTreeNode<T> leftLeftRotation(AVLTreeNode<T> k2){
        AVLTreeNode<T> k1;

        k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;

        k2.height = max(height(k2.left), height(k2.right)) + 1;
        k1.height = max(height(k1.left), k2.height) + 1;

        return k1;
    }

2.右子树的右子树插入节点(右右)

插入或删除一个节点后，根节点的右子树的右子树还有非空子节点，导致”根的右子树的高度”比”根的左子树的高度”大2，导致AVL树失去了平衡。例如，在上图中，由于根节点(5)的右子树(6)的右子树还有非空节点，而根节点(5)的左子树(2)没有子节点，导致了根节点(5)的右子树(6)高度比根节点(5)的左子树(2)高2，失去平衡。

理解了LL之后，RR就相当容易理解了。RR是与LL对称的情况！RR恢复平衡的旋转方法如下：

RR左旋

图中左边是旋转之前的树，右边是旋转之后的树。RR旋转也只需要一次即可完成。

给出RR的旋转代码如下：

    /**
     * RR：右右对应的情况(右单旋转)。
     */
    public AVLTreeNode<T> rightRightRotation(AVLTreeNode<T> k1){
        AVLTreeNode<T> k2;
        k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;

        k1.height = max(height(k1.left),height(k1.right)) + 1;
        k2.height = max(k1.height,height(k2.right)) + 1;
        return k2;
    }

3.左子树的右子树插入节点(左右)

插入或删除一个节点后，根节点的右子树的左子树还有非空子节点，导致”根的右子树的高度”比”根的左子树的高度”大2，导致AVL树失去了平衡。例如，在上图中，由于根节点(8)的左子树(5)的右子树还有非空节点，而根节点(8)无右子树，导致了根节点失去平衡。LR失去平衡的情况下，需要经过两次旋转才能让AVL树恢复平衡。

LR的旋转

第一次旋转是围绕”k1”进行的”RR旋转”，第二次是围绕”k3”进行的”LL旋转”。

给出LR的旋转代码如下所示：

    /**
     * LR: 左右对应的情况(左双旋转)
     */
    public AVLTreeNode<T> leftRightRotation(AVLTreeNode<T> k3){
        k3.left = rightRightRotation(k3.left);
        return leftLeftRotation(k3);
    }

4.右子树的左子树插入节点(右左)

插入或删除一个节点后，根节点的右子树的右子树还有非空子节点，导致”根的右子树的高度”比”根的左子树的高度”大2，导致AVL树失去了平衡。例如，在上图中，由于节点(10)的右子树(15)的左子树还有非空节点，而节点(10)的左子树为空，导致了节点失去平衡。RL是与LR的对称情况！RL恢复平衡的旋转方法如下：

RL的旋转

第一次旋转是围绕”k3”进行的”LL旋转”，第二次是围绕”k1”进行的”RR旋转”。

给出RL的旋转代码如下所示：

     /**
     * RL：右左对应的情况(右双旋转)。
     */
    public AVLTreeNode<T> rightLeftRotation(AVLTreeNode<T> k1){
        k1.right = leftLeftRotation(k1.right);
        return rightRightRotation(k1);
    }

#### 3. 插入操作

给出插入操作的代码如下：

     /**
     * 递归将结点插入到AVL树中，并返回根节点
     */
    private AVLTreeNode<T> insert(AVLTreeNode<T> tree, T key){
        if(tree == null){
            tree = new AVLTreeNode<>(key,null,null);
            if(tree == null){
                System.out.println("ERROR: create avltree node failed!");
                return null;
            }
        }else{
            int cmp = key.compareTo(tree.key);
            if(cmp < 0){
                //应将key插入到tree的左子树的情况
                tree.left = insert(tree.left,key);
                //插入节点后，如果AVL树失去平衡，则进行相应的调整
                if (height(tree.left) - height(tree.right) == 2){
                    if(key.compareTo(tree.left.key) < 0){
                        tree = leftLeftRotation(tree);
                    }else {
                        tree = leftRightRotation(tree);
                    }
                }
            }else if(cmp > 0){
                //应将key插入到tree的右子树的情况
                tree.right = insert(tree.right,key);
                //插入节点后，如果AVL树失去平衡，则进行相应的调整
                if (height(tree.right) - height(tree.left) == 2){
                    if(key.compareTo(tree.right.key) > 0){
                        tree = rightRightRotation(tree);
                    }else {
                        tree = rightLeftRotation(tree);
                    }
                }
            }else {
                System.out.println("添加失败：不允许添加相同的节点！");
            }
        }
        tree.height = max(height(tree.left), height(tree.right)) + 1;
        return tree;
    }

    public void insert(T key){
        mRoot = insert(mRoot,key);
    }

#### 4. 删除操作

对二叉查找树，我们知道删除的结点可能有三种情况：(1)为叶子结点，(2)左子树或右子树有一个为空，(3)左右子树都不空。假设删除节点为A。

对于（1）：直接删除即可。

对于（2）：删除的方法，A的父节点绕过A节点使其指向A左子树（右子树为空）、右子树（左子树为空时）。

对于（3）：一般的删除策略：用A的左子树最大数据或右子树最小数据（假设B节点）代替A节点的数据，并递归地删除B节点。

AVL的树的删除策略与二叉查找树的删除策略相似，只是删除节点后造成树失去平衡性，需要做平衡处理。

    /**
     * 删除结点(z)，返回根节点
     */
    private AVLTreeNode<T> remove(AVLTreeNode<T> tree, AVLTreeNode<T> z){
        //根为空 或者 没有要删除的节点，直接返回null。
        if(tree == null || z == null){
            return null;
        }
        int cmp = z.key.compareTo(tree.key);
        if(cmp < 0){
            //待删除的节点在"tree的左子树"中
            tree.left = remove(tree.left, z);
            // 删除节点后，若AVL树失去平衡，则进行相应的调节。
            if (height(tree.right) - height(tree.left) == 2){
                AVLTreeNode<T> r = tree.right;
                if(height(r.left) > height(r.right)){
                    tree = rightLeftRotation(tree);
                }else {
                    tree = rightRightRotation(tree);
                }
            }
        }else if(cmp > 0){
            //待删除的节点在"tree的右子树"中
            tree.right = remove(tree.right,z);
            if(height(tree.left) - height(tree.right) == 2){
                AVLTreeNode<T> l = tree.left;
                if(height(l.right) > height(l.left)){
                    tree = leftRightRotation(tree);
                }else {
                    tree = leftLeftRotation(tree);
                }
            }
        }else{
            //tree是对应要删除的节点
            // tree的左右孩子都非空
            if((tree.left != null) && (tree.right != null)){
                if(height(tree.left) > height(tree.right)){
                    // 如果tree的左子树比右子树高；则(01)找出tree的左子树中的最大节点;(02)将该最大节点的值赋值给tree。
                    //   (03)删除该最大节点。这类似于用"tree的左子树中最大节点"做"tree"的替身；
                    //   采用这种方式的好处是：删除"tree的左子树中最大节点"之后，AVL树仍然是平衡的。
                    AVLTreeNode<T> max = maximum(tree.left);
                    tree.key = max.key;
                    tree.left = remove(tree.left, max);
                }else{
                    // 如果tree的左子树不比右子树高(即它们相等，或右子树比左子树高,则(01)找出tree的右子树中的最小节点
                     //   (02)将该最小节点的值赋值给tree。
                     //   (03)删除该最小节点。
                     // 这类似于用"tree的右子树中最小节点"做"tree"的替身；
                     // 采用这种方式的好处是：删除"tree的右子树中最小节点"之后，AVL树仍然是平衡的。
                    AVLTreeNode<T> min = minimum(tree.right);
                    tree.key = min.key;
                    tree.right = remove(tree.right, min);
                }
            }else{
                AVLTreeNode<T> tmp = tree;
                tree = (tree.left != null) ? tree.left : tree.right;
                tmp = null;
            }
        }
        return tree;
    }

    public void remove(T key){
        AVLTreeNode<T> z;
        if((z = search(mRoot,key)) != null){
            mRoot = remove(mRoot, z);
        }
    }

    private AVLTreeNode<T> search(AVLTreeNode<T> x, T key){
        if(x == null){
            return x;
        }
        int cmp = key.compareTo(x.key);
        if(cmp < 0){
            return search(x.left, key);
        }else if(cmp > 0){
            return search(x.right, key);
        }else {
            return x;
        }
    }

    private AVLTreeNode<T> minimum(AVLTreeNode<T> tree){
        if(tree == null){
            return null;
        }
        while (tree.left != null){
            tree = tree.left;
        }
        return tree;
    }

    private AVLTreeNode<T> maximum(AVLTreeNode<T> tree){
        if(tree == null){
            return null;
        }
        while (tree.right != null){
            tree = tree.right;
        }
        return tree;
    }

AVL树的性能分析

性能优势：很显然，平衡二叉树的优势在于不会出现普通二叉查找树的最差情况。其查找的时间复杂度为O(logN)。

平衡二叉树的缺陷包含有：

很遗憾的是，为了保证高度平衡，动态插入和删除的代价也随之增加。红黑树是更加高效的查找结构。
所有二叉查找树结构的查找代价都与树高是紧密相关的，能否通过减少树高来进一步降低查找代价呢。我们可以通过多路查找树的结构来做到这一点。
在大数据量查找环境下(比如说系统磁盘里的文件目录，数据库中的记录查询等)，所有的二叉查找树结构(BST、AVL、RBT)都不合适。如此大规模的数据量（几G数据），全部组织成平衡二叉树放在内存中是不可能做到的。那么把这棵树放在磁盘中吧。问题就来了：假如构造的平衡二叉树深度有1W层。那么从根节点出发到叶子节点很可能就需要1W次的硬盘IO读写。大家都知道，硬盘的机械部件读写数据的速度远远赶不上纯电子媒体的内存。查找效率在IO读写过程中将会付出巨大的代价。在大规模数据查询这样一个实际应用背景下，平衡二叉树的效率就很成问题了。

AVL树

"AVL树总结"

AVL树

AVL树的Java实现

1. 节点

2.AVL树不平衡的情况

AVL树的性能分析

CATALOG

FEATURED TAGS

FRIENDS