大家好，我是讯享网，很高兴认识大家。

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; } 

讯享网

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

二叉搜索树的局限性就体现出来了，明显的看到第二个序列由二叉树退化为链表了，这样查找效率也从 $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; } 

输出

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 

这棵树长这个样子：

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

---

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$ 型，针对不同类型的失衡有不同类型的旋转策略。