高阶DS---AVL树详解（每步配图），高阶DS详解，AVL树的步骤与配图解析

温馨提示：这篇文章已超过474天没有更新，请注意相关的内容是否还可用！

摘要：本篇高阶DS内容将详细介绍AVL树，一种自平衡二叉搜索树。文章结合每步配图，清晰展示AVL树的构造、插入和删除操作。通过AVL树的平衡机制，确保在查找、插入和删除过程中保持树的平衡状态，从而提高数据操作的效率。本文旨在帮助读者深入理解AVL树的基本原理和应用。

前言：

AVL树的概念:

AVL树节点的定义：

AVL树的插入（重点）

AVL树的旋转：

（1）新节点插入较高左子树的左侧---右单旋

（2）新节点插入较高右子树的右侧---左单旋

（3）新节点插入较高左子树的右侧---左右双旋

（4）新节点插入较高右子树的左侧---右左双旋

总结：

AVL树的验证：

验证用例：

AVL树的删除（了解）：

AVL树性能分析：

结语：

前言：

如果有友友需要本文章的全部源码的话请前往AVL树源码

AVL树的概念:

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过 1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

（1）它的左右子树都是AVL树

（2）左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O（logN），搜索时间复杂度O(logN)。

例如下图就是一个AVL树圆圈外面的数字就是平衡因子，为右子树高度 - 左子树高度。

高阶DS---AVL树详解（每步配图），高阶DS详解，AVL树的步骤与配图解析第1张

AVL树节点的定义：

为了AVL树实现简单，AVL树节点在定义时维护一个平衡因子和采用孩子双亲表示法，具体节点定义如下：

因为在实际开发时我们都是树节点单独创建一个类不是很经常使用静态内部类，故我们这里就创建一个TreeNode类来实现。

public class TreeNode {
    public int val;//节点值
    public int bf;//AVL树的平衡因子
    public TreeNode left;//左孩子引用
    public TreeNode right;//右孩子引用
    public TreeNode parent;//父亲节点引用
    public TreeNode(int val){
        this.val = val;
    }
}

注意：

当前节点的平衡因子 = 右子树高度 - 左子树的高度。但是，不是每棵树，都必须有平衡因子，这只是其中的一种实现方式。

AVL树的插入（重点）

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：

（1）按照二叉搜索树的方式插入新节点。

（2）调整节点的平衡因子。

但是在插入节点后要更新平衡因子，这时AVL树的平衡性就可能会遭到破坏，我们就要进行调整。

假设插入节点为node，node的父亲节点为parent，在node节点插入后，parent节点的平衡因子一定要进行调整，在插入之前，parent的平衡因子分为三种情况：-1，0，1。

（1）如果cur插入到parent的左侧，只需给parent的平衡因子 -1 即可。

（2）如果cur插入到parent的右侧，只需给parent的平衡因子 +1 即可。

此时：parent的平衡因子可能有三种情况：0，正负1，正负2。对应分析如下：

（1）如果parent的平衡因子为0，说明插入之前parent的平衡因子为正负1，插入后被调整成0，此时满足AVL树的性质，插入成功，就不需要向上调整，因为对于上面的节点来说这颗子树的最大高度没有改变。

（2）如果parent的平衡因子为正负1，说明插入前parent的平衡因子一定为0，插入后被更新成正负1，此时以parent为根的树的高度增加，需要继续向上更新。

（3）如果parent的平衡因子为正负2，则parent的平衡因子违反平衡树的性质，需要对其进行旋转处理。

根据上面的分析我们可以先写出如下代码（大体框架），首先我们先根据二叉搜索树的查找节点方式找到要插入节点的父亲节点，插入节点后修改平衡因子，根据修改后平衡因子的情况分为三种情况。👍👍👍

public boolean insert(int val){
        //根据二叉搜索树查找节点的方式，找到插入点
        TreeNode node = new TreeNode(val);
        //根节点为空
        if(root == null){
            root = node;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        //parent始终是cur的父亲节点，当cur为null时parent就是我们要插入节点的父亲节点
        while(cur != null){
            if(cur.val > val){
                //去左子树找
                parent = cur;
                cur = cur.left;
            }else if(cur.val  
如果对上面代码的else部分为什么是这么旋转感到疑惑的话，可以先跳过，在介绍完下面AVL树的旋转后就明白了。  
AVL树的旋转： 
如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种： 
注意：下面我画的四张图大家一定一定要会画，总不可能记代码吧，没有意义。 
我最常用的例子节点是：60，30，a，b，c（其中a，b，c为满足要求的任意值） 
（1）新节点插入较高左子树的左侧---右单旋 
 
上面的图便是我们右单旋的全过程了，我们可以发现旋转完后这个AVL树变得平衡了，且需要修改的平衡因子只有两个subL和parent的平衡因子。 
具体代码如下： 
在这过程中subLR节点可能不存在故要来一次特判防止空指针异常，接着要分是根节点和不是根节点两种情况，如果不是根节点又要分是pParent（parent的父亲节点）的左子树还是右子树。主要要弄好指向和平衡因子的修改（经过分析和作图后发现调整后只有subL和parent平衡因子发生改变）。 
private void rotateRight(TreeNode parent){
        //右旋
        TreeNode subL = parent.left;//parent节点的左孩子节点
        TreeNode subLR = subL.right;//parent节点的左孩子节点的右孩子节点
        parent.left = subLR;
        //防止节点不存在，空指针异常
        if(subLR != null){
            subLR.parent = parent;
        }
        subL.right = parent;
        //在修改parent的父亲节点时，要提前记入下来防止丢失
        TreeNode pParent = parent.parent;
        parent.parent = subL;
        //如果parent是根节点,即没有父亲节点
        if(parent == root){
            root = subL;
            subL.parent = null;
        }else{
            //有父亲节点故要考虑其是父亲节点的左孩子还是右孩子
            if(pParent.left == parent){
                pParent.left = subL;
            }else{
                pParent.right = subL;
            }
            subL.parent = pParent;
        }
        //经过分析和作图发现调整后只有subL和parent平衡因子发生改变
        //subL平衡因子从-1变成0
        //parent平衡因子从-2变成0
        subL.bf = 0;
        parent.bf = 0;
    }
 （2）新节点插入较高右子树的右侧---左单旋
上图为我们左单旋的全过程，这个其实可以仿照我们右单旋的步骤来。具体代码如下：
用private进行封装，创建对应的孩子节点，进行下面个个参数的指向修改时一定要画图🌸🌸🌸，节点的选取可以仿照我上面画的，最后注意不要忘了修改对应节点的平衡因子。
这里教给大家一个记忆小技巧：对哪个节点进行旋转，新的parent节点的旋转方向（根据名字）节点要断掉。
 private void rotateLeft(TreeNode parent){
        //左旋
        //小技巧：对哪个节点进行旋转，新的parent节点的旋转方向(根据名字)节点要断掉
        TreeNode subR = parent.right;//parent的右孩子
        TreeNode subRL = subR.left;//parent的右孩子的左孩子
        //防止节点不存在空指针异常
        if(subRL != null){
            subRL.parent = parent;
        }
        //这里建议画图理解
        parent.right = subRL;
        subR.left = parent;
        //在修改parent的父亲节点时，要提前记入下来防止丢失
        TreeNode pParent = parent.parent;
        parent.parent = subR;
        if(parent == root){
            root = subR;
            subR.parent = null;
        }else{
            if(pParent.left == parent){
                pParent.left = subR;
            }else{
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
        subR.bf = 0;
        parent.bf = 0;
    }
 （3）新节点插入较高左子树的右侧---左右双旋
在有些情况下只进行左旋和右旋还并不能解决所有情况，例如下图，如果友友感兴趣的话可以自己试试，显然一次旋转完成不了。我们正确的旋转方式为左右双旋，先左旋再进行右旋。
正确旋转过程如下图。
下图只演示了subLR的平衡因子为-1的情况还有1和0的情况就交给友友们自己去完成了都差不多的👍👍👍 
代码如下：
这里特别注意我们传入左右旋的方法的参数是传入parent而不是其孩子节点，这个一定要弄清楚否则就错了，下面之所以没有bf == 0的情况是因为在 bf == 0 的情况下在rotateLeft方法和rotateRight方法下就已经吧要修改的bf修改完成了。但是不能if后面用else必须是else if，因为else会把bf == 0的情况收纳进去这样就出错了。 
 private void rotateLR(TreeNode parent){
        //左右双旋
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        int bf = subLR.bf;
        //bf的获取必须在旋转之前否则会因旋转而改变,旋转会改变对应的平衡因子
        rotateLeft(subL);
        rotateRight(parent);
        //画图，这里可以分为插在左边还是右边
        if(bf == -1){
            parent.bf = 1;
            subL.bf = 0;
            subLR.bf = 0;
        }else if(bf == 1){
            //bf == 1
            parent.bf = 0;
            subLR.bf = 0;
            subL.bf = -1;
        }
    }
 （4）新节点插入较高右子树的左侧---右左双旋
右左双旋的实现，友友们可以参考左右双旋。
具体流程和左右双旋差不多也有三种情况，bf为0，1，-1的三种情况，注意传入左右旋方法的参数是传入对应的parent节点。
对应代码如下：
 private void rotateRL(TreeNode parent){
        //右左双旋
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        int bf = subRL.bf;
        //bf的获取必须在旋转之前否则会因旋转而改变
        //旋转传入的父亲节点为原来的不是改变后的
        rotateRight(subR);
        rotateLeft(parent);
        //画图，这里可以分为插在左边还是右边
        if(bf == 1){
            parent.bf = -1;
            subRL.bf = 0;
            subR.bf = 0;
        }else if(bf == -1){
            // bf == -1
            subRL.bf = 0;
            parent.bf = 0;
            subR.bf = 1;
        }
    }
 总结：
新节点插入后，假设以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑：
1.pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR。
（1）当pSubR的平衡因子为1时，执行左单旋。
（2）当pSubR的平衡因子为-1时，执行右左双旋。
2.pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL。
（1）当pSubL的平衡因子为-1是，执行右单旋。
（2）当pSubL的平衡因子为1时，执行左右双旋。
即：pParent与其较高子树节点的平衡因子时同号时单旋转，异号时双旋转。
旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新。
AVL树的验证：
分为两步：
（1）验证其为二叉搜索树
如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
（2）验证其为平衡树
1.每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
2.节点的平衡因子是否计算正确
对应代码如下：
 public boolean isBalance(TreeNode root){
        if(root == null) return true;
        int heightL = height(root.left);
        int heightR = height(root.right);
        if(heightR - heightL != root.bf){
            System.out.println(root.val + ":的平衡因子计算错误");
            return false;
        }
        return Math.abs(heightL - heightR)