数据结构学习笔记 6-1 手撕AVL树 与 LeetCode真题（Java）

喜欢该类型文章可以给博主点个关注，博主会持续输出此类型的文章，知识点很全面，再加上LeetCode的真题练习，每一个LeetCode题解我都写了详细注释，比较适合新手入门数据结构与算法，后续也会更新进阶的文章。
课件参考—开课吧《门徒计划》

6-1 手撕AVL树

AVL树是目前为止学习到的第一个高级数据结构。

AVL树是 二叉排序树 的升级。

前导—二叉排序树

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。

二叉排序树在二叉树的基础上做了一点调整。

性质：

• $左子树<根节点$
• $右子树>根节点$

拿着一颗二叉排序树进行中序遍历，它就是一个升序的序列；用途：解决与排名相关的检索需求。

二叉排序树就是一个天然的二分查找，每次查找都可以将规模缩小 $\frac{n}{2}$，查找元素的时间复杂度稳定在 $O(logn)$。

二叉排序树的插入

待插入的节点是 $10$：

先与根节点比较大小，小于则在左子树：

再依次跟后续节点进行比较：

此时 $10<3$，应放到 $3$ 的右子树：

二叉排序树的删除

1. 删除叶子节点

因为没有子节点，所以直接删除无任何影响。

2. 删除出度为 $1$ 的节点

删除 $3$，则把 $3$ 的子节点 $10$ 作为 $3$ 的父节点 $17$ 的子节点，也就是将 $17$ 的孙子升辈为儿子：

3. 删除出度为 $2$ 的节点

两个名词：前驱，后继，对一个树中序遍历：[..., 19, 20, 28, ...]，对于根节点 $20$ 来说，排在 $20$ 前面的数字就是前驱，排在 $20$ 后面的数字就是后继。

对于二叉排序树来说，根节点的前驱节点就是左子树中的最大值，后继节点就是右子树中的最小值；

而左子树最右侧的节点就是左子树的最大值，右子树最左侧的节点就是右子树的最小值。

那么怎么删呢？我们可以用待删除节点的前驱或者后继中的任何一个节点进行替换，此时问题转换成了删除出度为 $1$ 的节点，因为前驱一定没有右子树，后继一定没有左子树，所以前驱和后继一定是没有子树或者只有一个子树。

此时我们直接根据下标把待删除节点 $20$ 和前驱节点 $19$ 进行替换，再把替换后的 $20$ 按照删除出度为 $1$ 的节点删除即可。

但这样替换不是违背了二叉排序树的性质吗？此时我们可以把待删除的节点先更新为前驱节点的值，再在左子树中找到前驱节点，将其删除。

二叉排序树代码实现

// 二叉搜索树
public class BinarySortTree {

    static Node NIL = new Node(); // 作用等同于链表中的哨兵节点 防止有些节点为null时 不好操作

    // 对NIL进行初始化
    private static void init_NIL() {
        // todo
        NIL.value = -1;
        // 把NIL的左子树和右子树都指向自己 这样即使操作NIL的左子树和右子树也不会出现异常
        NIL.left = NIL.right = NIL;
        NIL.h = 0;
    }

    // 获取节点
    private static Node getNewNode(int value) {
        Node p = new Node();
        p.value = value;
        p.left = p.right = NIL;
        p.h = 1;
        return p;
    }

    // 插入节点
    private static Node insert(Node root, int target) {
        if (root == NIL) return getNewNode(target);
        if (root.value == target) return root;
        if (root.value > target) {
            root.left = insert(root.left, target);
        } else {
            root.right = insert(root.right, target);
        }
        update_h(root); // 因为插入了节点 所以在回溯的时候需要更新一下所有节点的树高
        return root;
    }

    // 删除节点
    private static Node delete(Node root, int target) {
        if (root == NIL) return root;
        if (root.value > target) {
            root.left = delete(root.left, target);
        } else if (root.value < target) {
            root.right = delete(root.right, target);
        } else { // root.value == target 执行删除
            // 分类讨论 3种情况
            // 出度为0
            if (root.left == NIL && root.right == NIL) {
                root = NIL;
                return root;
            } else if (root.left == NIL || root.right == NIL) { // 出度为1
                return root.left != NIL ? root.left : root.right; // 直接把该节点的子节点返回给父节点
            } else { // 出度为2
                Node temp = get_pre(root.left); // 获取前驱节点
                root.value = temp.value; // 将待删除节点值更新为前驱节点值
                root.left = delete(root.left, temp.value); // 在左子树中找到前驱节点值并删除
            }
        }
        update_h(root); // 同样需要在回溯时更新每个节点的高度
        return root;
    }

    // 获取前驱节点
    private static Node get_pre(Node root) {
        Node temp = root;
        // 找到左子树中最右侧的节点
        while (temp.right != NIL) temp = temp.right;
        return temp;
    }

    // 更新树高
    private static void update_h(Node root) {
        root.h = Math.max(root.left.h, root.right.h) + 1;
    }

    // 中序遍历
    private static void in_order(Node root) {
        if (root == NIL) return;
        in_order(root.left);
        System.out.print(root.value + " ");
        in_order(root.right);
    }

    public static void main(String[] args) {
        init_NIL();
        Node root = NIL;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Random rand = new Random();
        for (int i = 0; i < n; i++) {
            int val = rand.nextInt(100);
            System.out.println("\ninsert " + val + " to BinarySortTree");
            root = insert(root, val);
            in_order(root);
        }
    }
}

class Node {
    int value;
    int h; // 存一下每个节点的树高 为AVL树做铺垫
    Node left, 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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

下面我们对比这两个序列插入在二叉搜索树后的样子：

二叉搜索树的局限性就体现出来了，明显的看到第二个序列由二叉树退化为链表了，这样查找效率也从 $O(logn)$ 退化为 $O(n)$了；

至此，为了解决二叉搜索树退化的问题，我们就引出了AVL树。

AVL树基础知识

平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树。

平衡树：为了避免二叉搜索树退化成链表的状态；AVL树是最基础的平衡树，学习起来相对比较简单。

前两个性质和二叉搜索树一模一样，而多了第三个性质：$|H(left)-H(right)|⩽1$，左子树减去右子树的差值不能超过 $1$。

AVL树—左旋

圆圈代表单个节点，三角形代表某一颗子树。

由于现在 $K3$ 下有两颗子树，假设这两颗子树树高为 $2$，所以此时这棵树一定处于失衡状态，所以我们要选择一个节点进行旋转，此时我们抓着 $K3$ 进行旋转，但单纯的把 $K3$ 拎上去 变为根节点，$K3$ 的直系子节点就会变成 $K1、A、B$，变成了三叉树，$K1$ 和 $A$ 同为 $K3$ 的左节点，起冲突了，所以我们要把 $K3$ 的左子树也就是 $A$ 这棵子树分给 $K1$，因为最开始 $A$ 就是 $K1$ 的右子树，所以肯定比 $K1$ 大，放在 $K1$ 的右节点位置；这样整棵树就平衡了。

重点：抓着哪一个节点进行旋转。

AVL树—右旋

就是左旋的对称操作，不过多赘述。

在插入全部元素后，从下往上回溯时进行旋转。

AVL树—失衡类型

同色为对称的结构，树中带颜色的三角形子树就代表着这棵树过高了。

• $LL$ 型

  

  对于上方这棵AVL树是否平衡，我们可以先对未旋转的 $LL$ 型树做一下公式推导：

  $K2=h_A+1$

  $K3=max(h_C+h_A)+1$

  $K2=K3+2$

  $h_A+1=max(h_C+h_A)+3$

  $h_A=h_B+1=max(h_C+h_A)+2$

  再把上述答案代入到旋转后的树，一定是平衡的。

• $LR$ 型

  

  同样我们对未旋转的 $LR$ 型树做一下公式推导：

  $K3=max(h_B+h_C)+1$

  $K3=h_A+1$

  $h_A=max(h_B+h_C)$

  $K2=K3+1=h_A+2$

  $K2=h_D+2$

  $h_A=h_D$

  再将这些公式代入旋转后的树判断，肯定也是平衡的。

$RR$ 型和 $RL$ 型跟上面两个是对称的，就不过多推导了。

AVL树代码实现

// AVL树 => 在二叉搜索树的基础上判断是否平衡 进行左旋和右旋
public class BinarySortTree {

    static Node NIL = new Node(); // 作用等同于链表中的哨兵节点 防止有些节点为null 不好操作

    // 对NIL进行初始化
    private static void init_NIL() {
        // todo
        NIL.value = -1;
        // 把NIL的左子树和右子树都指向自己 这样即使操作NIL的左子树和右子树也不会出现异常
        NIL.left = NIL.right = NIL;
        NIL.h = 0;
    }

    // 获取节点
    private static Node getNewNode(int value) {
        Node p = new Node();
        p.value = value;
        p.left = p.right = NIL;
        p.h = 1;
        return p;
    }

    // 插入节点
    private static Node insert(Node root, int target) {
        if (root == NIL) return getNewNode(target);
        if (root.value == target) return root;
        if (root.value > target) {
            root.left = insert(root.left, target);
        } else {
            root.right = insert(root.right, target);
        }
        update_h(root); // 因为插入了节点 所以在回溯的时候需要更新一下所有节点的树高
        return maintain(root); // 插入元素后 回溯时进行平衡判断、调整
    }

    // 删除节点
    private static Node delete(Node root, int target) {
        if (root == NIL) return root;
        if (root.value > target) {
            root.left = delete(root.left, target);
        } else if (root.value < target) {
            root.right = delete(root.right, target);
        } else { // root.value == target 执行删除
            // 分类讨论 3种情况
            // 出度为0
            if (root.left == NIL && root.right == NIL) {
                root = NIL;
                return root;
            } else if (root.left == NIL || root.right == NIL) { // 出度为1
                return root.left != NIL ? root.left : root.right; // 直接把该节点的子节点返回给父节点
            } else { // 出度为2
                Node temp = get_pre(root.left); // 获取前驱节点
                root.value = temp.value; // 将待删除节点值更新为前驱节点值
                root.left = delete(root.left, temp.value); // 在左子树中找到前驱节点值并删除
            }
        }
        update_h(root); // 同样需要在回溯时更新每个节点的高度
        return maintain(root); // 删除元素后 回溯时进行平衡判断、调整
    }

    // 获取前驱节点
    private static Node get_pre(Node root) {
        Node temp = root;
        // 找到左子树中最右侧的节点
        while (temp.right != NIL) temp = temp.right;
        return temp;
    }

    // 更新树高
    private static void update_h(Node root) {
        root.h = Math.max(root.left.h, root.right.h) + 1;
    }

    // 左旋
    private static Node left_rotate(Node root) {
        Node temp = root.right;
        root.right = temp.left;
        temp.left = root;
        update_h(root);
        update_h(temp); // 更新节点高度
        return temp;
    }

    // 右旋
    private static Node right_rotate(Node root) {
        Node temp = root.left;
        root.left = temp.right;
        temp.right = root;
        update_h(root);
        update_h(temp); // 更新节点高度
        return temp;
    }

    // 判断当前节点往下看是否失衡
    private static Node maintain(Node root) {
        if (Math.abs(root.left.h - root.right.h) <= 1) return root; // 平衡
        if (root.left.h > root.right.h) { // 左子树更高 失衡条件是L
            if (root.left.right.h > root.left.left.h) { // 失衡条件是LR型
                // 先左旋 再右旋
                root.left = left_rotate(root.left);
            }
            // 没走上面的if 则是LL型 直接右旋即可
            root = right_rotate(root);
        } else { // 右子树更高 失衡条件是R
            if (root.right.left.h > root.right.right.h) { // 失衡条件是RL型
                // 先右旋 再左旋
                root.right = right_rotate(root.right);
            }
            // 没走上面的if 则是RR型 直接左旋即可
            root = left_rotate(root);
        }
        return root;
    }

    // 中序遍历
    private static void in_order(Node root) {
        if (root == NIL) return;
        in_order(root.left);
        System.out.print(root.value + " ");
        in_order(root.right);
    }

    // 前序遍历进行输出 方便观察树是否平衡
    private static void output(Node root) {
        if (root == NIL) return;
        System.out.println(root.value + " " + "(" + root.h + ") " + "|" + root.left.value + ", " + root.right.value);
        output(root.left);
        output(root.right);
    }

    public static void main(String[] args) {
        init_NIL();
        Node root = NIL;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Random rand = new Random();
        for (int i = 0; i < n; i++) {
            int val = rand.nextInt(100);
            System.out.println("\ninsert " + val + " to BinarySortTree");
            root = insert(root, val);
            output(root);
        }
    }
}

class Node {
    int value;
    int h; // 存一下每个节点的树高 为AVL树做铺垫
    Node left, 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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

输出

7

insert 5 to BinarySortTree
5 (1) |-1, -1

insert 55 to BinarySortTree
5 (2) |-1, 55
55 (1) |-1, -1

insert 65 to BinarySortTree
55 (2) |5, 65
5 (1) |-1, -1
65 (1) |-1, -1

insert 38 to BinarySortTree
55 (3) |5, 65
5 (2) |-1, 38
38 (1) |-1, -1
65 (1) |-1, -1

insert 86 to BinarySortTree
55 (3) |5, 65
5 (2) |-1, 38
38 (1) |-1, -1
65 (2) |-1, 86
86 (1) |-1, -1

insert 71 to BinarySortTree
55 (3) |5, 71
5 (2) |-1, 38
38 (1) |-1, -1
71 (2) |65, 86
65 (1) |-1, -1
86 (1) |-1, -1

insert 22 to BinarySortTree
55 (3) |22, 71
22 (2) |5, 38
5 (1) |-1, -1
38 (1) |-1, -1
71 (2) |65, 86
65 (1) |-1, -1
86 (1) |-1, -1
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

这棵树长这个样子：

这棵树超级平衡！代码实现的超级完美！

---

LeetCode真题

经典面试题—二叉搜索树系列

LeetCode面试题 04.06. 后继者

难度：mid

方法一：中序遍历

我们需要对原树进行一次中序遍历，再找目标值后面的值。

思路很简单，就是对树进行中序遍历，然后在遍历的过程中找到 $p$，然后再看一下它的下一个节点是谁；

但这样会存在问题，在中序遍历中，我们不一定可以立即确定指定节点 $p$ 的下一个节点是谁，有可能 $p$ 的下一个节点是经过回溯很多次才会出现；所以为了解决这个问题，我们换一种思路，在每次递归过程中记录一下当前节点的前一个节点，在递归时判断这个节点的前一个节点是否为 $p$，那么该节点就是 $p$ 的后继。

方法二：利用二叉搜索树的性质

• 如果 $root.val⩽p.val$，则说明 $p$ 的后继肯定在右子树，因为左子树的值都小于 $root$，所以我们直接往右子树递归搜索后继。
• 如果 $root.val>p.val$，则后继可能在左子树中，也可能就是 $root$，所以直接往左子树递归，先在左子树中寻找比 $p$ 大的节点，如果发现 $root.val⩽p.val$，然后再去右子树中寻找。

LeetCode题解：两种方法代码实现

---

LeetCode450. 删除二叉搜索树中的节点

难度：mid

这道题就是我们上面代码写的删除操作，需要分类讨论三种情况：

• 出度为 $0$
• 出度为 $1$
• 出度为 $2$（需要前驱 / 后继节点）

根据不同的出度选择不一样的策略，直接看代码吧。

LeetCode题解：代码实现

---

LeetCode1382. 将二叉搜索树变平衡

难度：mid

给我们一颗已经失衡的二叉搜索树，让我们把它变平衡，我们可以把树遍历一遍存到数组中，然后重新建树，有两种实现方法：

• 手撕AVL树 (不建议)，重新建立一颗AVL树，就是一颗平衡二叉搜索树（需要手写一个AVL树，比较麻烦）

• 递归建树 (最优解)，我们中序遍历一遍二叉搜索树，那么得到的值一定是有序的，所以我们以数组的中间值作为根节点进行递归建树，根节点的左右节点分别是中间值左半部分的中间值 和 中间值右半部分的中间值，这样递归建完就能保证这棵树平衡了。

  

LeetCode题解：代码实现

---

LeetCode108. 将有序数组转换为二叉搜索树

难度：easy

把有序数组转换为AVL树（平衡二叉搜索树）。

跟上一题一模一样，本题已经给了有序数组，所以直接根据数组的中间值递归建树即可。

LeetCode题解：代码实现

---

LeetCode98. 验证二叉搜索树

难度：mid

朴素思想：把这棵树中序遍历，将中序遍历的值记录到数组中，判断是否有序，但我们可以取巧的遍历：

在中序遍历时，判断当前节点是否大于前一个节点，如果大于，说明满足，继续遍历；否则直接返回 $false$。

跟LeetCode面试题 04.06. 后继者的方法一：中序遍历思想差不多。

LeetCode题解：代码实现

---

LeetCode501. 二叉搜索树中的众数

难度：easy

在一个含有重复值的二叉搜索树中找到众数（出现次数最多的值）。

朴素思想：中序遍历二叉搜索树，把有序的值存到数组中，在数组中找众数，但题中有一段话：

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

所以我们可以在递归的过程中进行判断，判断该数出现的次数，小于目前最大出现次数的不管，等于目前最大出现次数 则加到答案中，大于目前最大出现次数 则清空元素 存入新答案。

利用这棵二叉搜索树的性质：相同元素在这棵二叉搜索树中一定挨着。

LeetCode题解：两种方法代码实现

---

LeetCode剑指 Offer 33. 二叉搜索树的后序遍历序列

难度：mid

我们可以依据现有的后续遍历结果，将这棵树进行中序遍历，判断是否有序即可。

LeetCode题解：代码实现

---

LeetCode1008. 前序遍历构造二叉搜索树

难度：mid

我们可以通过前序遍历的结果，确定根节点的左子树区间和右子树区间，从而找到左子树的根节点和右子树的根节点，重新确定区间，递归建树。

前序遍历的第一个值一定是根节点，找到第一个比根节点大的值 $i$，$[root+1,i-1]$ 就是左子树的区间，$[i,preorder.length-1]$ 就是右子树的区间。

LeetCode题解：代码实现

---

LeetCode面试题 04.09. 二叉搜索树序列

难度：hard

只要父节点出现在子节点之前就可以，可以把这道题转换成递归搜索树。

对每一列进行排列组合，先生成左子树的排列组合，再生成右子树的排列组合，再与根节点拼接。

LeetCode题解：代码实现

---

总结

AVL树 就是 平衡的二叉搜索树，本节的选题都是跟二叉搜索树相关的，只要把二叉搜索树理解透彻了，那么学习AVL树就会轻松许多了。

二叉搜索树比较复杂的点在于删除，根据出度的不同对应不同的删除策略。

AVL树就是在二叉搜索树上增加了平衡的机制，具体对应左旋和右旋，而失衡条件又分为四种：$LL$ 型、$LR$ 型、$RR$ 型 和 $RL$ 型，针对不同类型的失衡有不同类型的旋转策略。