AVL树

在理解AVL之前一定理解二叉搜索树这个东西，下面是详细地址

二叉搜索树地址（仅供学习参考）

想必到这里，我们已经深刻理解了二叉搜索树（BST），那我们必然知道二叉搜索树的时间复杂度为:O(logN) 那我们来思考一个极端情况如下图所示：

当我们只在二叉搜索树一段插入（即插入的每一个值越来越大）很明显，此时的二叉树已经变成了一个链表，此时的时间复杂度嗯。。。咳～咳～～

  作为程序猿我们当然想维护一刻完美的二叉树，更利于我们的操作如下图：

当然也没必要一定这么完美，就像找女朋友一样，再好的妹子也要用屁股剪断自己拉的💩，所以两情相悦才是最重要的，不要迷失在花花世界哟～

    在程序猿手中尤其是Java程序员手中，因为自己可以手动new一个对象，所以我们一直致力于创造一种尽可能平衡的BST,于是我们加以限制，始终保持BST任一左右子树高度相等使得其满足时间复杂度O(logN)。
  于是经过我们的不断努力，创造了ABL树如下图：

AVL树:

• 它的左右子树都是AVL树
• 左右子树高度之差(简称平衡因子)的绝对值不超过1

以下是四种失衡状态：（LL,LR,RL,RR）以下两张图来源于网络仅供学习参考

---

关于这些失衡状态，每一种都有极为巧妙的办法使其重新变得平衡，

LL失衡旋转

//右单旋（LL状态对应的旋转操作）
    private AVLNode llRotating(AVLNode root){
        //这三个步骤完成交换
        AVLNode newRoot = root.left;
        root.left = newRoot.right;
        newRoot.right = root;
        //这两个步骤完成高度更新
        root.height = Math.max(root.left.height , root.right.height) + 1;
        newRoot.height = Math.max(newRoot.left.height , root.height) + 1;
        return newRoot;
    }
1
2
3
4
5
6
7
8
9
10
11

---

RR失衡旋转

//左单旋（RR状态对应的旋转操作）
    private AVLNode rrRotating(AVLNode root){
        //这三个步骤完成交换
        AVLNode newRoot = root.right;
        root.right = newRoot.left;
        newRoot.left = root;
        //这俩步骤完成高度更新
        root.height = Math.max(root.left.height , root.right.height) + 1;
        newRoot.height = Math.max(root.height , newRoot.right.height) + 1;
        return newRoot;
    }
1
2
3
4
5
6
7
8
9
10
11

---

LR失衡旋转

//LR旋转（LR状态旋转）
    private AVLNode lrRotating(AVLNode root){
        //其中ll与rr方法上面有介绍
        root.left = rrRotating(root.left);
        return llRotating(root);
    }
1
2
3
4
5
6

---

RL失衡旋转

//RL旋转（RL状态旋转）
    private AVLNode rlRotating(AVLNode root){
        root.right = llRotating(root.right);
        return rrRotating(root);
    }
1
2
3
4
5

---

下面正式来见一下插入的操作

1. 插入一个新节点可能会导致某个位置发生上述的始终不平衡状态
2. 想必看了下面代码你会发现为什么会多一个专门求高度的方法插入完了会有解答
3. 再插入新节点造成不平衡状态之后我们根据每种不同状态执行相应旋转操作就好了

public void insert(int val){
        root = insert(root , val);
    }

    private AVLNode insert(AVLNode root, int val) {
        if (root == null){
            root = new AVLNode(null , null , val);
        }else {
            if (root.val > val){
                root.left = insert(root.left , val);
                //看这里，是不是疑问为什么不能是-2：解：如果值比节点val小肯定插在左面那么造成不平衡的位置一定发生在左子树
                if (getHeight(root.left) - getHeight(root.right) == 2){
                    if (root.left.val > val){
                        root = llRotating(root);
                    }else {
                        root = lrRotating(root);
                    }
                }

            }else if (root.val < val){
                root.right = insert(root.right , val);
                if (getHeight(root.right) - getHeight(root.left) == 2){
                    if (root.right.val < val){
                        root = rrRotating(root);
                    }else {
                        root = rlRotating(root);
                    }
                }
            }else {
                //此时节点值与插入值相等
                //可以抛异常throw new NoSuchElementException("老哥哥这个值有了");
                System.out.println("这个值有了");
            }
        }
        root.height = Math.max(getHeight(root.left) , getHeight(root.right)) + 1;
        return root;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

是不是对插入时的状态还是很迷糊，一下想不通，来，俺给你手动画一个图看一下。

上述是左面的两种状态，右面也是一样的可以自行理解一下。

现在明白为什么要getHeight（）了吧，如果是空值的话不就没法处理了嘛，所以其实上面的旋转操作里面也是不能直接root.height来获取高度哟，给你一张反思券，好好反思一下为啥没发现，文章最后有具体操作的完整代码可供参考

---

嗯。。。那么猜你应该已经明白了AVL树，删除自己解决吧。。。
哈哈哈开个玩笑，来我们继续完成最后的删除操作
注：AVL本质也是BST所以他的插入删除操作其实与BST是一样的，只要在完成相关操作后，重新处理保持AVL树状态(即做旋转操作)

下面来正式接触删除操作（相比于BST操作，我们将重新介绍另一个删除操作）

1. 判断这个值在哪边，当在一侧删除后，便可能变成不平衡状态，我们重新进行维护，值的考虑的是假设左面删除，那么必然是右面的高度更高
2. 如果一端高假设右端 ，呢么有可能是左子树的左子树或右子树引起的RL或RR状态，我们执行相对应的操作即可
3. 假设找到了带删除的值，那么就像BST那样删除就好即找到左子树最小或右子树最大进行替换
4. 当然我想你发现了华点，是的没错，因为只在一端找引发不平衡概率会加大，索引在删除该节点时，我们在更高的一段找到来执行删除操作，这样会让树更平衡，提高效率

public void delete(int val){
        if (contains(val)){
            root = delete(root , val);
        }else {
            System.out.println("待删除的这个值不存在哦～");
        }
    }
    private AVLNode delete(AVLNode root , int val){
        if (root == null){
            System.out.println("树是空的，没地方删");
            return null;
        }
        if (val < root.val){
            root.left = delete(root.left , val);
            //与插入一样，完成删除操作后，来维持AV，既然删了左子树，那么右面高度肯定是更高的
            if (getHeight(root.right) - getHeight(root.left) == 2){
                if (getHeight(root.right.right) > getHeight(root.right.left)){
                    //相对当前树根是RR状，具体画图在同目录md中有详细解释
                    root = rrRotating(root);
                }else {
                    //此时在RL状态
                    root = rlRotating(root);
                }
            }
        }else if (val > root.val){
            root.right = delete(root.right , val);
            if (getHeight(root.left) - getHeight(root.right) == 2){
                if (getHeight(root.left.left) > getHeight(root.left.right)){
                    root = llRotating(root);
                }else {
                    root = lrRotating(root);
                }
            }
        }else {
            if (root.left != null && root.right != null){
                if (getHeight(root.left) > getHeight(root.right)){
                    int lMax = max(root.left).val;
                    root.val = lMax;
                    delete(root.left , lMax);
                }else {
                    int rMin = min(root.right).val;
                    root.val = rMin;
                    delete(root.right , rMin);
                }
            }else {
                root = root.left == null ? root.right : root.left;
            }
        }
        root.height = Math.max(getHeight(root.left) , getHeight(root.right)) + 1;
        return root;
    }
    private AVLNode min(AVLNode root){
        if (root.left == null){
            return root;
        }
        return min(root.left);
    }
    private AVLNode max(AVLNode root){
        if (root.right == null){
            return root;
        }
        return max(root.right);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

截止目前AVL树相关操作我们就处理完了后续将更新红黑树的操作，敬请期待

本文完整代码将至于Gitee仅供学习参考切勿搬运，后续将更新测试，敬请期待

本文绿白圆圈的图片资源均来源于网络，仅供学习参考，如有侵权请私信我会删，求求别跟
俺要天价赔偿费，俺一个裤x子都要穿三年😭
1
2