数据结构与算法|数据结构学习笔记 6-1 手撕AVL树与 LeetCode真题（Java） AVL树|二叉搜索树|leetcode|java|数

6-1 手撕AVL树 AVL树是目前为止学习到的第一个高级数据结构。
AVL树是 二叉排序树 的升级。
前导—二叉排序树

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

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

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

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

文章图片

拿着一颗二叉排序树进行中序遍历，它就是一个升序的序列；用途：解决与排名相关的检索需求。
二叉排序树就是一个天然的二分查找，每次查找都可以将规模缩小n 2 \frac{n}{2} 2n?，查找元素的时间复杂度稳定在O ( l o gn ) O(log\ n) O(log n)。
二叉排序树的插入
待插入的节点是10 10 10：

文章图片

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

文章图片

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

文章图片

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

文章图片

二叉排序树的删除

文章图片

1. 删除叶子节点因为没有子节点，所以直接删除无任何影响。
2. 删除出度为1 1 1 的节点删除3 3 3，则把3 3 3 的子节点10 10 10 作为3 3 3 的父节点17 17 17 的子节点，也就是将17 17 17 的孙子升辈为儿子：

文章图片

3. 删除出度为2 2 2 的节点两个名词：前驱，后继，对一个树中序遍历：[..., 19, 20, 28, ...]，对于根节点20 20 20 来说，排在20 20 20 前面的数字就是前驱，排在20 20 20 后面的数字就是后继。
对于二叉排序树来说，根节点的前驱节点就是左子树中的最大值，后继节点就是右子树中的最小值；
而左子树最右侧的节点就是左子树的最大值，右子树最左侧的节点就是右子树的最小值。

文章图片

那么怎么删呢？我们可以用待删除节点的前驱或者后继中的任何一个节点进行替换，此时问题转换成了删除出度为1 1 1 的节点，因为前驱一定没有右子树，后继一定没有左子树，所以前驱和后继一定是没有子树或者只有一个子树。
此时我们直接根据下标把待删除节点20 20 20 和前驱节点19 19 19 进行替换，再把替换后的20 20 20 按照删除出度为1 1 1 的节点删除即可。
但这样替换不是违背了二叉排序树的性质吗？此时我们可以把待删除的节点先更新为前驱节点的值，再在左子树中找到前驱节点，将其删除。

文章图片

二叉排序树代码实现

// 二叉搜索树 public class BinarySortTree {static Node NIL = new Node(); // 作用等同于链表中的哨兵节点防止有些节点为null时不好操作// 对NIL进行初始化 private static void init_NIL() { // todo NIL.value = https://www.it610.com/article/-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 =https://www.it610.com/article/= 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 ( l o gn ) O(log\ n) O(log n) 退化为O ( n ) O(n) O(n)了；
至此，为了解决二叉搜索树退化的问题，我们就引出了AVL树。
AVL树基础知识

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

平衡树：为了避免二叉搜索树退化成链表的状态；AVL树是最基础的平衡树，学习起来相对比较简单。
前两个性质和二叉搜索树一模一样，而多了第三个性质： ∣ H ( l e f t ) ? H ( r i g h t ) ∣ ? 1 |H(left)-H(right)|\leqslant1 ∣H(left)?H(right)∣?1，左子树减去右子树的差值不能超过1 1 1。

文章图片

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

文章图片

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

文章图片

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

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

文章图片

L L LL LL 型

文章图片

对于上方这棵AVL树是否平衡，我们可以先对未旋转的L L LL LL 型树做一下公式推导：
K 2 = h A + 1 K2=h_A + 1 K2=hA?+1
K 3 = m a x ( h C + h A ) + 1 K3 = max(h_C+h_A)+1 K3=max(hC?+hA?)+1
K 2 = K 3 + 2 K2=K3+2 K2=K3+2
h A + 1 = m a x ( h C + h A ) + 3 h_A+1=max(h_C+h_A)+3 hA?+1=max(hC?+hA?)+3
h A = h B + 1 = m a x ( h C + h A ) + 2 h_A=h_B+1=max(h_C+h_A)+2 hA?=hB?+1=max(hC?+hA?)+2
再把上述答案代入到旋转后的树，一定是平衡的。
L R LR LR 型

文章图片

同样我们对未旋转的L R LR LR 型树做一下公式推导：
K 3 = m a x ( h B + h C ) + 1 K3=max(h_B+h_C)+1 K3=max(hB?+hC?)+1
K 3 = h A + 1 K3=h_A+1 K3=hA?+1
h A = m a x ( h B + h C ) h_A=max(h_B+h_C) hA?=max(hB?+hC?)
K 2 = K 3 + 1 = h A + 2 K2=K3+1=h_A+2 K2=K3+1=hA?+2
K 2 = h D + 2 K2=h_D+2 K2=hD?+2
h A = h D h_A=h_D hA?=hD?
再将这些公式代入旋转后的树判断，肯定也是平衡的。

R R RR RR 型和R L RL RL 型跟上面两个是对称的，就不过多推导了。
AVL树代码实现

// AVL树 => 在二叉搜索树的基础上判断是否平衡进行左旋和右旋 public class BinarySortTree {static Node NIL = new Node(); // 作用等同于链表中的哨兵节点防止有些节点为null 不好操作// 对NIL进行初始化 private static void init_NIL() { // todo NIL.value = https://www.it610.com/article/-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 =https://www.it610.com/article/= 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.right; 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.left; 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; }

文章图片

LeetCode真题经典面试题—二叉搜索树系列 LeetCode面试题 04.06. 后继者
难度：mid
方法一：中序遍历
我们需要对原树进行一次中序遍历，再找目标值后面的值。

文章图片

思路很简单，就是对树进行中序遍历，然后在遍历的过程中找到p p p，然后再看一下它的下一个节点是谁；
但这样会存在问题，在中序遍历中，我们不一定可以立即确定指定节点p p p 的下一个节点是谁，有可能p p p 的下一个节点是经过回溯很多次才会出现；所以为了解决这个问题，我们换一种思路，在每次递归过程中记录一下当前节点的前一个节点，在递归时判断这个节点的前一个节点是否为p p p，那么该节点就是p p p 的后继。
方法二：利用二叉搜索树的性质

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

LeetCode题解：两种方法代码实现
LeetCode450. 删除二叉搜索树中的节点
难度：mid
这道题就是我们上面代码写的删除操作，需要分类讨论三种情况：

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

根据不同的出度选择不一样的策略，直接看代码吧。
LeetCode题解：代码实现
LeetCode1382. 将二叉搜索树变平衡
难度：mid
给我们一颗已经失衡的二叉搜索树，让我们把它变平衡，我们可以把树遍历一遍存到数组中，然后重新建树，有两种实现方法：

手撕AVL树 (不建议)，重新建立一颗AVL树，就是一颗平衡二叉搜索树（需要手写一个AVL树，比较麻烦）
递归建树 (最优解)，我们中序遍历一遍二叉搜索树，那么得到的值一定是有序的，所以我们以数组的中间值作为根节点进行递归建树，根节点的左右节点分别是中间值左半部分的中间值和中间值右半部分的中间值，这样递归建完就能保证这棵树平衡了。

文章图片

LeetCode题解：代码实现
LeetCode108. 将有序数组转换为二叉搜索树
难度：easy
把有序数组转换为AVL树（平衡二叉搜索树）。
跟上一题一模一样，本题已经给了有序数组，所以直接根据数组的中间值递归建树即可。
LeetCode题解：代码实现
LeetCode98. 验证二叉搜索树
难度：mid
朴素思想：把这棵树中序遍历，将中序遍历的值记录到数组中，判断是否有序，但我们可以取巧的遍历：
在中序遍历时，判断当前节点是否大于前一个节点，如果大于，说明满足，继续遍历；否则直接返回f a l s e false false。
跟LeetCode面试题 04.06. 后继者的方法一：中序遍历思想差不多。
LeetCode题解：代码实现
LeetCode501. 二叉搜索树中的众数
难度：easy
在一个含有重复值的二叉搜索树中找到众数（出现次数最多的值）。
朴素思想：中序遍历二叉搜索树，把有序的值存到数组中，在数组中找众数，但题中有一段话：

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

所以我们可以在递归的过程中进行判断，判断该数出现的次数，小于目前最大出现次数的不管，等于目前最大出现次数则加到答案中，大于目前最大出现次数则清空元素存入新答案。
利用这棵二叉搜索树的性质：相同元素在这棵二叉搜索树中一定挨着。
LeetCode题解：两种方法代码实现
LeetCode剑指 Offer 33. 二叉搜索树的后序遍历序列
难度：mid
我们可以依据现有的后续遍历结果，将这棵树进行中序遍历，判断是否有序即可。
LeetCode题解：代码实现
LeetCode1008. 前序遍历构造二叉搜索树
难度：mid
我们可以通过前序遍历的结果，确定根节点的左子树区间和右子树区间，从而找到左子树的根节点和右子树的根节点，重新确定区间，递归建树。
前序遍历的第一个值一定是根节点，找到第一个比根节点大的值i i i， [ r o o t + 1 ,i ? 1 ] [root+1,\ i-1] [root+1, i?1] 就是左子树的区间， [ i ,p r e o r d e r . l e n g t h ? 1 ] [i,\ preorder.length-1] [i, preorder.length?1] 就是右子树的区间。

文章图片

LeetCode题解：代码实现
LeetCode面试题 04.09. 二叉搜索树序列
难度：hard
只要父节点出现在子节点之前就可以，可以把这道题转换成递归搜索树。
对每一列进行排列组合，先生成左子树的排列组合，再生成右子树的排列组合，再与根节点拼接。
LeetCode题解：代码实现
总结

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

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

【数据结构与算法|数据结构学习笔记 6-1 手撕AVL树与 LeetCode真题（Java）】AVL树就是在二叉搜索树上增加了平衡的机制，具体对应左旋和右旋，而失衡条件又分为四种： L L LL LL 型、 L R LR LR 型、 R R RR RR 型和R L RL RL 型，针对不同类型的失衡有不同类型的旋转策略。