面试让我手写红黑树( 三 ) _红黑树

测试结果
/----- 94 /----- 89 | | /----- 73 | ----- 72 /----- 64 | ----- 63 32 | /----- 18 | /----- 14 ----- 7 ----- 6 /----- 94 /----- 89 | ----- 73 /----- 72 | ----- 63 32 | /----- 18 | /----- 14 ----- 7 ----- 6 Process finished with exit code 0

这个案例就是删除双节点的案例，删除了节点64以后，节点72被提取上来使用。读者伙伴也可以尝试删除其他节点测试验证

三、AVL 树
AVL树历史
在计算机科学中，AVL 树以其两位苏联发明家Georgy Adelson-Velsky和 Evgenii Landis的名字命名，他们在 1962 年的论文“信息组织算法”中发表了它。它是一种自平衡二叉搜索树(BST)，这是发明的第一个这样的数据结构。
1. AVL树数据结构
AVL 自平衡二叉树的出现，其目的在于解决二叉搜索树退化成链表的问题。当我们向BST二叉搜索树顺序存入1、2、3、4、5、6、7个元素时，它会退化成一条链表，因而失去树查询的时间复杂度，所以我们需要AVL树平衡树高。如图所示

文章插图

那么AVL树是怎么平衡树高的呢？
当二叉树的左右分支树高差不为1时，需要进行左旋或者右旋，来调衡树高。这有点像开车的时候，如果车头偏左就往右打方向盘，车头偏右就往左打方向盘是一个道理。那这个方向盘(左旋、右旋)是怎么打的呢，主要分以下四种情况；
左旋（新增节点6）右旋（新增节点1）左旋+右旋（新增节点4）右旋+左旋（新增节点3）

文章插图

文章插图

条件：节点4，平衡因子为-2，左旋条件：节点3，平衡因子为2，右旋条件：节点3，平衡因子为2，右旋。但当节点2平衡因子-1先左旋。条件：节点2，平衡因子为-2，左旋。但当节点5平衡因子1先右旋。

节点树高：以节点4为说明，最长的左右分支节点个数，就是节点4的最大树高。这里节点4左右孩子节点最长路径都为2，所以它的树高为2 。同理可计算其他节点树高。
平衡因子：通过当前节点的左右子节点作差计算平衡因子，之后AVL树通过平衡因子，定义了什么时候进行左旋和右旋。
源码地址：https://github.com/fuzhengwei/java-algorithms
本章源码：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/tree

2. AVL树代码实现
对于 AVL 树的实现与 BST 二叉搜索树相比，在树的节点定义上多了一个树高的属性。也有些AVL树使用的是平衡因子的属性，就是通过树高计算后的结果。树节点代码结构如下；

public class Node { public Class clazz; public Integer value; public Node parent; public Node left; public Node right; // AVL 树所需属性 public int height; }

接下来小傅哥就分别通过代码讲解下一颗AVL树的左旋、右旋、左旋+右旋、右旋+左旋的代码操作。不要担心这没有多复杂，只要你能搞清楚左旋，就能搞清楚右旋。两旋弄懂组合就没啥难度了。

源码地址：https://github.com/fuzhengwei/java-algorithms
本章源码：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/stack
动画演示：https://visualgo.net/zh/bst?slide=1 —— AVL树初次理解还是比较困难的，可以结合学习内容的同时做一些动画演示。

2.1 左旋
图解左旋操作；它就是一种摘链更换调整节点的处理过程，小傅哥把它分解展示，整个过程如下；

文章插图

代码实现

protected Node rotateLeft(Node node) { Node temp = node.right; temp.parent = node.parent; node.right = temp.left; if (node.right != null) { node.right.parent = node; } temp.left = node; node.parent = temp; if (temp.parent == null) { root = temp; } else { if (temp.parent.left == node) { temp.parent.left = temp; } else { temp.parent.right = temp; } } return temp; }