作者：小傅哥
博客：https://bugstack.cn
沉淀、分享、成长，让自己和他人都能有所收获！😄
一、前言：挂在树上！不知道你经历过HashMap的夺命连环问！
为啥，面试官那么喜欢让你聊聊 HashMap？因为 HashMap 涉及的东西广，用到的数据结构多，问题延展性好，一个 HashMap 就能聊下来80%的数据结构了。而且面试 HashMap 能通过你对红黑树的了解定位出你哪个级别的研发人员。
而红黑树的知识点可以说是非常庞大，在学习红黑树时也不能一下就能掌握，甚至很程序员压根就没搞明白红黑树，只是背下来它的几条限定规则而已。
其实一开始我也是这样！ 不过总感觉这块的知识点不搞个明明白白，就闹心。因为不可能一个理科的东西，是需要死记硬背搞下来的。所以在翻阅资料、文档、历史、典籍，找到红黑树的演化过程，它是从2-3树演变而来，而2-3树、AVL树，这类B-树，也就是 BalancedTree 平衡树。它们都是为了解决 BST 二叉搜索树不自平衡而来的产物。
那么现在清楚了，要想搞定红黑树，让懂了就是真的懂，就需要把前面这些知识搞定，并且除了理论还能用落地的案例代码编写出来，才是悟透。好，那么接下来，小傅哥就带着你一起搞定这点事
二、BST 树Binary Search Tree历史
二叉搜索树算法是由包括 PF Windley、Andrew Donald Booth、Andrew Colin、Thomas N. Hibbard 在内的几位研究人员独立发现的。该算法归功于 Conway Berners-Lee 和 David Wheeler ，他们在 1960 年使用它在磁带中存储标记数据。 最早和流行的二叉搜索树算法之一是 Hibbard 算法。
1. 二叉搜索树数据结构二叉搜索树（Binary Search Tree），也称二叉查找树。如果你看见有序二叉树（Ordered Binary tree）、排序二叉树（Sorted Binary Tree）那么说的都是一个东西。
代码语言：txt复制
若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；任意节点的左、右子树也分别为二叉查找树；二叉搜索树在日常开发中使用的场景还是比较多的，例如基于组合模式实现的规则引擎，它就是一颗二叉搜索树。但类似这样的开发中用到的二叉树场景，都是基于配置生成，所以组合出来的节点也更加方便控制树高和平衡性。这与 Java API HashMap 中的红黑树这样为了解决插入节点后仍保持树的平衡性是有所不同的。
所以二叉搜索树也是一颗没有经过调衡的基础性数据结构，在一定概率上它完成有可能退化成链表，也就是从近似O(logn)的时间复杂度退化到O(n)。关于二叉搜索树的平衡解决方案，包括；AVL树、2-3树、红黑树等，小傅哥会在后续的章节继续实现。
2. 二叉搜索树结构实现二叉搜索树是整个树结构中最基本的树，同时也是树这个体系中实现起来最容易的数据结构。但之所以要使用基于二叉搜索树之上的其他树结构，主要是因为使用数据结构就是对数据的存放和读取。那么为了提高吞吐效率，则需要尽可能的平衡元素的排序，体现在树上则需要进行一些列操作，所以会有不同的结构树实现。
而实现二叉搜索树是最好的基础学习，了解基本的数据结构后才更容易扩展学习其他树结构。
源码地址：https://github.com/fuzhengwei/java-algorithms本章源码：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/tree2.1 树枝定义代码语言：java复制public Integer value;public Node parent;public Node left;public Node right;用于组成一颗树的节点，则需要包括；值和与之关联的三角结构，一个父节点、两个孩子节点。如果是AVL树还需要树高，红黑树还需要染色标记。2.2 插入节点代码语言：java复制public Node insert(int e) {if (null == root) {root = new Node(e, null, null, null);size++;return root;}// 索引出待插入元素位置，也就是插入到哪个父元素下Node parent = root;Node search = root;while (search != null && search.value != null) {parent = search;if (e < search.value) {search = search.left;} else {search = search.right;}}// 插入元素Node newNode = new Node(e, parent, null, null);if (parent.value > newNode.value) {parent.left = newNode;} else {parent.right = newNode;}size++;return newNode;}首先判断插入元素时候是否有树根，没有则会把当前节点创建出一颗树根来。如果当前树是有树根的，则对插入元素与当前树进行一个节点遍历操作，找到元素可以插入的索引位置 parent（挂到这个父节点下）。也就是 search 搜索过程。最后就是插入元素，通过给插入值创建一个 Node 节点，并绑定它的父元素，以及把新元素挂到索引到的 parent 节点下。2.3 索引节点代码语言：java复制public Node search(int e) {Node node = root;while (node != null && node.value != null && node.value != e) {if (e < node.value) {node = node.left;} else {node = node.right;}}return node;}值查找的过程，就是对二叉搜索树的遍历，不断的循环节点，按照节点值的左右匹配，找出最终相当的值节点。2.4 删除节点代码语言：java复制public Node delete(int e) {Node delNode = search(e);if (null == delNode) return null;return delete(delNode);}private Node delete(Node delNode) {if (delNode == null) return null;Node result = null;if (delNode.left == null) {result = transplant(delNode, delNode.right);} else if (delNode.right == null) {result = transplant(delNode, delNode.left);} else {// 因为删除的节点，有2个孩子节点，这个时候找到这条分支下，最左侧做小的节点。用它来替换删除的节点Node miniNode = getMiniNode(delNode.right);if (miniNode.parent != delNode) {// 交换位置，用miniNode右节点，替换miniNodetransplant(miniNode, miniNode.right);// 把miniNode 提升父节点，设置右子树并进行挂链。替代待删节点miniNode.right = delNode.right;miniNode.right.parent = miniNode;}// 交换位置，删除节点和miniNode 可打印测试观察；System.out.println(this);transplant(delNode, miniNode);// 把miniNode 提升到父节点，设置左子树并挂链miniNode.left = delNode.left;miniNode.left.parent = miniNode;result = miniNode;}size--;return result;}private Node getMinimum(Node node) {while (node.left != null) {node = node.left;}return node;}private Node transplant(Node delNode, Node addNode) {if (delNode.parent == null) {this.root = addNode;}// 判断删除元素是左/右节点else if (delNode.parent.left == delNode) {delNode.parent.left = addNode;} else {delNode.parent.right = addNode;}// 设置父节点if (null != addNode) {addNode.parent = delNode.parent;}return addNode;}2.4.1 删除单节点代码语言：txt复制
待删除节点14，判断此节点的父节点的孩子节点，哪个等于14，找出左右把待删节点的右孩子节点，挂到删除节点的右节点给待删节点的右孩子节点，设置上父节点2.4.2 删除双节点代码语言：txt复制
待删除节点64，含有双子节点，则需要根据第一个右子节点查找最小左子节点。从89到72，如果有比72还小的左子节点，继续排查。排查到节点72，将72这个准备替换待删元素的节点，与右子节点73进行位置交换，过程与 4.1 相同。使用交换函数 transplant最后是进行节点72与待删节点64的交换过程，更换三角关系，父节点、左子节点、右子节点。3. 二叉搜索树功能测试为了方便观察树结构的变化，这里小傅哥找了一些资料资料，一种是我们可以通过程序来打印（类似大家之前打印99乘法表，另外是使用线上的可视化图：https://visualgo.net/zh/bst?slide=1）
3.1 随机插入元素代码语言：java复制@Testpublic void test_binary_search_tree() {BinarySearchTree tree = new BinarySearchTree();for (int i = 0; i < 10; i++) {tree.insert(new Random().nextInt(100));}System.out.println(tree);}测试结果
代码语言：java复制 /----- 91 |\----- 78 /----- 74 |\----- 6761 |/----- 51 \----- 40 |/----- 28 \----- 14 \----- 7 Process finished with exit code 0因为你测试时的随机数不同，可能会出现很多不同结构的二叉搜索树，也可能是一个类似链表结构的退化树。3.2 插入并且删除代码语言：java复制@Testpublic void test_insert_delete(){BinarySearchTree tree = new BinarySearchTree();tree.insert(32);tree.insert(7);tree.insert(64);tree.insert(63);tree.insert(89);tree.insert(72);tree.insert(94);tree.insert(6);tree.insert(14);tree.insert(18);tree.insert(73);System.out.println(tree);// 删除单节点，只有一个孩子的父节点// tree.delete(14);// 删除双节点，拥有二个孩子的父节点tree.delete(64);System.out.println(tree);}测试结果
代码语言：java复制 /----- 94 /----- 89 ||/----- 73 |\----- 72 /----- 64 |\----- 6332 |/----- 18 |/----- 14 \----- 7 \----- 6 /----- 94 /----- 89 |\----- 73 /----- 72 |\----- 6332 |/----- 18 |/----- 14 \----- 7 \----- 6Process 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树平衡树高。如图所示
代码语言：txt复制
那么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/tree2. AVL树代码实现对于 AVL 树的实现与 BST 二叉搜索树相比，在树的节点定义上多了一个树高的属性。也有些AVL树使用的是平衡因子的属性，就是通过树高计算后的结果。树节点代码结构如下；
代码语言：java复制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 左旋图解左旋操作；它就是一种摘链更换调整节点的处理过程，小傅哥把它分解展示，整个过程如下；
代码语言：txt复制
代码实现
代码语言：java复制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;}左旋的作用，相当于通过向上迁移树高差大于1的右子节点来降低树高的操作。通过节点4拿到父节点2和右子节点5，把父节点2和右子节点5建立关联节点5的左子节点，相当于是大于4小于4的那么一个值，只不过这里不体现。那么这个节点4的左子节点，应该被迁移到节点3的右子节点上。整理节点5的关系，左子节点为4。左子节点4的父节点为5如果说迁移上来的节点5无父节点，那么它就是父节点 root = temp迁移上来的节点5，找到原节点4是对应父节点的左子节点还是右子节点，对应的设置节点5的左右位置2.2 右旋图解右旋操作；它就是一种摘链更换调整节点的处理过程，小傅哥把它分解展示，整个过程如下；
代码语言：txt复制
代码实现
代码语言：java复制protected Node rotateRight(Node node) {Node temp = node.left;temp.parent = node.parent;node.left = temp.right;if (node.left != null) {node.left.parent = node;}temp.right = 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;}右旋的作用，相当于通过向上迁移树高差大于1的右子节点来降低树高的操作。通过节点3拿到父节点4和左子节点2，把父节点7和左子节点2建立关联节点2的右子节点，相当于是大于2小于3的那么一个值，只不过这里不体现。那么这个节点2的右子节点，应该被迁移到节点3的左子节点上。整理节点2的关系，右子节点为3。右子节点3的父节点为2如果说迁移上来的节点2无父节点，那么它就是父节点 root = temp迁移上来的节点2，找到原节点3是对应父节点的左子节点还是右子节点，对应的设置节点2的左右位置2.3 左旋 + 右旋之所以会有左旋 + 右旋，是因为一次右旋操作没法平衡树高，而这种树的不平衡节点的左子节点的右子节点过长，所以要把不平衡节点的左子节点向左旋转一次，之后再进行右旋操作。
代码语言：txt复制
代码实现
代码语言：java复制if (factor(node.left) >= 0) {Node temp = super.rotateRight(node);refreshHeight(temp.right);refreshHeight(temp);} else {Node temp = super.rotateLeft(node.left);refreshHeight(temp.left);refreshHeight(temp);node.left = temp;temp = super.rotateRight(node);refreshHeight(temp.right);refreshHeight(temp);}2.4 右旋 + 左旋之所以会有右旋 + 左旋，是因为一次左旋操作没法平衡树高，而这种树的不平衡节点的右子节点的左子节点过长，所以要把不平衡节点的右子节点向右旋转一次，之后再进行左旋操作。
代码语言：txt复制
代码实现
代码语言：java复制if (factor(node.right) = 0) {if (this.items[idx] < e) break;this.items[idx + 1] = this.items[idx];--idx;}this.items[idx + 1] = e;++this.number;}// ... 省略部分代码}2-3树的几点元素需要包括；一个数组的元素集合、元素的序号、孩子元素。因为一个节点最多可临时放入3个元素，那么就会最多有4个孩子元素，所以孩子元素也是一个数组并且在构造函数中按照4个元素进行初始化。由于本身2-3树插入元素的开始阶段，并不是直接创建一个新的节点，而是在初始化的数组空间中存入元素。所以在节点中提供了一个插入元素的方法 insert 来处理新增元素。另外2-3树的节点类，还提供了一个方便查询的方法。包括：获取左边元素、中间元素、右边元素，以及最小值、最大值和判断是否有孩子节点。这些内容可以源码。2.2 拆分节点当一个节点内有3个元素的时候，就要发起拆分东西，拆分的过程分为；
对3个节点的中间节点，插入到父节点上。剩余2个节点创建出新的节点。建立父节点和新创建的2个节点间关系。整个操作流程如图所示
代码语言：txt复制
2.1 插入父节点代码语言：java复制private Node_2_3 split(Node_2_3 node, Node_2_3 parent) {if (parent == null) {parent = new Node_2_3(node);}parent.insert(node.getMiddleItem());Node_2_3[] newNodes = this.triangle(node);this.replaceChild(parent, node, newNodes[0], newNodes[1]);return parent;}整个2-3树拆分的过程就是在 split 这个方法里，第一步解决了是否有父节点，没有则创建。之后将原节点的中间值插入到父节点中。接下来的操作就是拆分新节点和更换孩子节点建立新连接。2.2 拆分新节点代码语言：java复制private Node_2_3[] triangle(Node_2_3 node) {Node_2_3[] newNodes = new Node_2_3[2];newNodes[0] = new Node_2_3(node.items[0]);newNodes[1] = new Node_2_3(node.items[2]);if (!node.isLeaf()) {// 左孩子newNodes[0].children[0] = node.children[0];newNodes[0].children[1] = node.children[1];// 右孩子newNodes[1].children[0] = node.children[2];newNodes[1].children[1] = node.children[3];}return newNodes;}基于传递进来的节点，将节点的左右孩子创建新节点，如果这个孩子节点还有分支节点，则一并更新。2.3 建立新连接代码语言：java复制private void replaceChild(Node_2_3 parent, Node_2_3 oldChild, Node_2_3 child01, Node_2_3 child02) {if (oldChild == parent.children[0]) {parent.children[3] = parent.children[2];parent.children[2] = parent.children[1];parent.children[1] = child02;parent.children[0] = child01;} else if (oldChild == parent.children[1]) {parent.children[3] = parent.children[2];parent.children[2] = child02;parent.children[1] = child01;} else {parent.children[3] = child02;parent.children[2] = child01;}}建立新连接需要判断这个节点 oldChild 是父节点的左、中、右，之后进行依次的更换。如拆分节点的介绍图中，用到的就是 parent.children[1] = child02;parent.children[0] = child01; 两步操作过程。2.3 新增节点代码语言：java复制public void insert(int e) {// 记录元素elementList.add(e);// 插入元素if (root == null) {root = new Node_2_3(e);} else {root = insert(e, root);if (root.number == 3) {root = split(root, null);}}}private Node_2_3 insert(int e, Node_2_3 parent) {if (parent.isLeaf()) {parent.insert(e);return parent;}Node_2_3 child = null;if (parent.number == 1) {if (e < parent.getMinItem()) {child = insert(e, parent.getLeft());} else {child = insert(e, parent.getMiddle());}} else {if (e < parent.getMinItem()) {child = insert(e, parent.getLeft());} else if (e > parent.getMiddleItem()) {child = insert(e, parent.getRight());} else {child = insert(e, parent.getMiddle());}}if (child.number == 3) {return this.split(child, parent);}return parent;}新增节点的过程就比较简单了，一种是使用递归找到可以插入的位置，另外一种就是 where 循环。我们再BST、AVL两种数据结构种都是用了 where 循环。在2-3树中 insert 方法递归到对应的插入位置后，开始插入元素。当插入元素结束后判断这个节点是否已经达到了3个节点，如果是则进行拆分。拆分就调用了上面的步骤3. 2-3树结构测试为了让读者更好的理解2-3树的结构，小傅哥在程序的控制台打印了插入的过程。网上没有2-3树在线的动画演示，如果读者看到也可以留言给小傅哥
代码语言：java复制@Testpublic void test_insert_incr() {Tree_2_3 tree = new Tree_2_3();for (int i = 1; i