红黑树为什么是8_红黑树和b树和b+树的区别

红黑树比 AVL 树具体更高效在哪里？ 　　不要说是颜色标识，具体点 　　类似问题：红黑树与普通的平衡二叉树除了颜色到底有什么区别？为什么要引入红黑树，它比普通的平衡二叉树究竟好在哪？ 　　作者：小傅哥 博客：https://bugstack.cn 沉淀、分享、成长，让自己和他人都能有所收获！ 　　一、前言：挂在树上！ 　　为啥，面试官那么喜欢让你聊聊 HashMap？因为 HashMap 涉及的东西广，用到的数据结构多，问题延展性好，一个 HashMap 就能聊下来80%的数据结构了。而且面试 HashMap 能通过你对红黑树的了解定位出你哪个级别的研发人员。 　　而红黑树的知识点可以说是非常庞大，在学习红黑树时也不能一下就能掌握，甚至很程序员压根就没搞明白红黑树，只是背下来它的几条限定规则而已。 　　其实一开始我也是这样！ 不过总感觉这块的知识点不搞个明明白白，就闹心。因为不可能一个理科的东西，是需要死记硬背搞下来的。所以在翻阅资料、文档、历史、典籍，找到红黑树的演化过程，它是从2-3树演变而来，而2-3树、AVL树，这类B-树，也就是 BalancedTree 平衡树。它们都是为了解决 BST 二叉搜索树不自平衡而来的产物。 　　那么现在清楚了，要想搞定红黑树，让懂了就是真的懂，就需要把前面这些知识搞定，并且除了理论还能用落地的案例代码编写出来，才是悟透。好，那么接下来，小傅哥就带着你一起搞定这点事 　　二、BST 树 　　二叉搜索树算法是由包括 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）那么说的都是一个东西。

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；任意节点的左、右子树也分别为二叉查找树； 　　二叉搜索树在日常开发中使用的场景还是比较多的，例如基于组合模式实现的规则引擎，它就是一颗二叉搜索树。但类似这样的开发中用到的二叉树场景，都是基于配置生成，所以组合出来的节点也更加方便控制树高和平衡性。这与 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/tree 　　2.1 树枝定义 　　用于组成一颗树的节点，则需要包括；值和与之关联的三角结构，一个父节点、两个孩子节点。如果是AVL树还需要树高，红黑树还需要染色标记。 　　2.2 插入节点 　　首先判断插入素时候是否有树根，没有则会把当前节点创建出一颗树根来。如果当前树是有树根的，则对插入素与当前树进行一个节点遍历操作，找到素可以插入的索引位置 parent（挂到这个父节点下）。也就是 search 搜索过程。最后就是插入素，通过给插入值创建一个 Node 节点，并绑定它的父素，以及把新素挂到索引到的 parent 节点下。 　　2.3 索引节点 　　值查找的过程，就是对二叉搜索树的遍历，不断的循环节点，按照节点值的左右匹配，找出最终相当的值节点。 　　2.4 删除节点 　　2.4.1 删除单节点 　　

待删除节点14，判断此节点的父节点的孩子节点，哪个等于14，找出左右把待删节点的右孩子节点，挂到删除节点的右节点给待删节点的右孩子节点，设置上父节点 　　2.4.2 删除双节点 　　

待删除节点64，含有双子节点，则需要根据第一个右子节点查找最小左子节点。从89到72，如果有比72还小的左子节点，继续排查。排查到节点72，将72这个准备替换待删素的节点，与右子节点73进行位置交换，过程与 4.1 相同。使用交换函数 transplant最后是进行节点72与待删节点64的交换过程，更换三角关系，父节点、左子节点、右子节点。 　　3. 二叉搜索树功能测试 　　为了方便观察树结构的变化，这里小傅哥找了一些资料资料，一种是我们可以通过程序来打印（类似大家之前打印99乘法表，另外是使用线上的可视化图：https://visualgo.net/zh/bst?slide=1） 　　3.1 随机插入素 　　测试结果 　　因为你测试时的随机数不同，可能会出现很多不同结构的二叉搜索树，也可能是一个类似链表结构的退化树。 　　3.2 插入并且删除 　　测试结果 　　这个案例就是 删除双节点 的案例，删除了节点64以后，节点72被提取上来使用。读者伙伴也可以尝试删除其他节点测试验证 　　三、AVL 树 　　在计算机科学中，AVL 树以其两位苏联发明家Georgy Adelson-Velsky和 Evgenii Landis的名字命名，他们在 1962 年的论文“信息组织算法”中发表了它。它是一种自平衡二叉搜索树(BST)，这是发明的第一个这样的数据结构。 　　1. AVL树数据结构 　　AVL 自平衡二叉树的出现，其目的在于解决二叉搜索树退化成链表的问题。当我们向BST二叉搜索树顺序存入个素时，它会退化成一条链表，因而失去树查询的时间复杂度，所以我们需要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树使用的是平衡因子的属性，就是通过树高计算后的结果。树节点代码结构如下； 　　接下来小傅哥就分别通过代码讲解下一颗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 左旋 　　图解左旋操作；它就是一种摘链更换调整节点的处理过程，小傅哥把它分解展示，整个过程如下；

　　代码实现 　　左旋的作用，相当于通过向上迁移树高差大于1的右子节点来降低树高的操作。通过节点4拿到父节点2和右子节点5，把父节点2和右子节点5建立关联节点5的左子节点，相当于是大于4小于4的那么一个值，只不过这里不体现。那么这个节点4的左子节点，应该被迁移到节点3的右子节点上。整理节点5的关系，左子节点为4。左子节点4的父节点为5如果说迁移上来的节点5无父节点，那么它就是父节点 root = temp迁移上来的节点5，找到原节点4是对应父节点的左子节点还是右子节点，对应的设置节点5的左右位置 　　2.2 右旋 　　图解右旋操作；它就是一种摘链更换调整节点的处理过程，小傅哥把它分解展示，整个过程如下；

　　代码实现 　　右旋的作用，相当于通过向上迁移树高差大于1的右子节点来降低树高的操作。通过节点3拿到父节点4和左子节点2，把父节点7和左子节点2建立关联节点2的右子节点，相当于是大于2小于3的那么一个值，只不过这里不体现。那么这个节点2的右子节点，应该被迁移到节点3的左子节点上。整理节点2的关系，右子节点为3。右子节点3的父节点为2如果说迁移上来的节点2无父节点，那么它就是父节点 root = temp迁移上来的节点2，找到原节点3是对应父节点的左子节点还是右子节点，对应的设置节点2的左右位置 　　2.3 左旋 + 右旋 　　之所以会有左旋 + 右旋，是因为一次右旋操作没法平衡树高，而这种树的不平衡节点的左子节点的右子节点过长，所以要把不平衡节点的左子节点向左旋转一次，之后再进行右旋操作。

　　代码实现 　　2.4 右旋 + 左旋 　　之所以会有右旋 + 左旋，是因为一次左旋操作没法平衡树高，而这种树的不平衡节点的右子节点的左子节点过长，所以要把不平衡节点的右子节点向右旋转一次，之后再进行左旋操作。

　　代码实现 　　3. AVL树功能测试 　　为了验证AVL树的实现正确与否，这里我们做一下随机节点的插入，如果它能一直保持平衡，那么它就是一颗可靠 AVL 平衡树。 　　单测试 　　测试结果 　　随机插入30个节点，每个节点的顺序已经打印，经过AVL左右旋调衡后，二叉结构始终保持树高平衡因子不超过1，那么验证通过。 　　四、2-3树 　　这时候大部分资料会用2-3树来讲解红黑树，不过又不去实现一个2-3树，只是用了一个理论套另外一个理论。虽然能从理解上多一些参考，但始终感觉没有抓手呀。对于理科思维来说，你得给我东西呀。老是整这悬得楞的 谁能受了。所以这里我们先来用Java实现一个2-3树，有了基础再学习红黑树 　　1. 2-3树数据结构 　　2–3树是一种树型数据结构，由约翰·霍普克洛夫特于1970年发明。它通过在一个节点存放1-2个素来平衡树高。从而也使2-3树存在2叉节点和3叉节点。

　　这里要提到一点，在BST二叉搜索树可能退化成链表的基础上。引出了自平衡二叉树，也就是包括上一章实现的AVL树和Java API HashMap中用到的红黑树，它们都属于BalancedTree，也统称为B树，平衡的意思。 　　而本章实现的2-3树也是一种简单的平衡树，其中每个具有子节点（内部节点）的节点要么有两个子节点（2 节点）和一个数据素，要么有三个子节点（3 节点）和两个数据素。另外 2-3 树是3阶B 树，2-3-4 树是4阶B树。 　　在实现2-3树之前，先通过图稿演示下在2-3树中顺序插入1、2、3、4、5、6、7，七个素时，2-3树的调衡处理。

2-3 树的插入过程与 BST 树类似，会通过树的左右节点大小，找到自己的插入位置。一个节点可以右1-3个素，但当素个数为3时，则需要调衡。把三个节点的中间节点晋升上来，其余两个节点为子节点。如果进行一次调衡后，上一层父节点达到3个素，则需要2次调衡，来满足2-3树的规则。 　　咋样，是不看过这个图之后对于2-3树的实现已经有感觉了，想动手写写试试了？源码地址：https://github.com/fuzhengwei/java-algorithms本章源码：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/tree 　　2. 2-3树结构实现 　　2-3 树的实现并不复杂，但在实现前要思考 以下几个问题；Node 节点属性信息都包括什么？插入值，是否需要创建新的 Node？插入后，节点内有3个素后，怎么迁移素？ 　　2.1 节点定义 　　2-3树的几点素需要包括；一个数组的素集合、素的序号、孩子素。因为一个节点最多可临时放入3个素，那么就会最多有4个孩子素，所以孩子素也是一个数组并且在构造函数中按照4个素进行初始化。由于本身2-3树插入素的开始阶段，并不是直接创建一个新的节点，而是在初始化的数组空间中存入素。所以在节点中提供了一个插入素的方法 insert 来处理新增素。另外2-3树的节点类，还提供了一个方便查询的方法。包括：左边素、中间素、右边素，以及最小值、最大值和判断是否有孩子节点。这些内容可以源码。 　　2.2 拆分节点 　　当一个节点内有3个素的时候，就要发起拆分东西，拆分的过程分为；对3个节点的中间节点，插入到父节点上。剩余2个节点创建出新的节点。建立父节点和新创建的2个节点间关系。 　　整个操作流程如图所示

　　2.1 插入父节点 　　整个2-3树拆分的过程就是在 split 这个方法里，第一步解决了是否有父节点，没有则创建。之后将原节点的中间值插入到父节点中。接下来的操作就是拆分新节点和更换孩子节点建立新连接。 　　2.2 拆分新节点 　　基于传递进来的节点，将节点的左右孩子创建新节点，如果这个孩子节点还有分支节点，则一并更新。 　　2.3 建立新连接 　　建立新连接需要判断这个节点 oldChild 是父节点的左、中、右，之后进行依次的更换。如拆分节点的介绍图中，用到的就是 两步操作过程。 　　2.3 新增节点 　　新增节点的过程就比较简单了，一种是使用递归找到可以插入的位置，另外一种就是 where 循环。我们再BST、AVL两种数据结构种都是用了 where 循环。在2-3树中 insert 方法递归到对应的插入位置后，开始插入素。当插入素结束后判断这个节点是否已经达到了3个节点，如果是则进行拆分。拆分就调用了上面的步骤 　　3. 2-3树结构测试 　　为了让读者更好的理解2-3树的结构，小傅哥在程序的控制台打印了插入的过程。网上没有2-3树在线的动画演示，如果读者看到也可以留言给小傅哥 　　顺序插入10个节点，如果这是一颗BST树，它将会退化成链表。那么我们使用自平衡的2-3树，来看看它的插入效果。 　　测试效果 　　有了这样的数据结构示意，是不是再来看2-3树就非常清晰了。—— 我说过，理科生 + 技术，不要只抛理论，要看效果的！东西到手了，能拿捏了，再补充理论。 　　五、红黑树 　　红黑树（Red Black Tree）是一种自平衡二叉查找树，于 1972 年由 Rudolf Bayer 发明的对称二叉B树演化而来，并以2-3-4树、2-3树流行。最终在 1978 年由 Leonidas J. Guibas 和 Robert Sedgewick 从对称二叉 B 树中推导出红黑树。PS：之所以选择“红色”，是因为它是作者在Xerox PARC工作时可用的彩色激光打印机产生的最好看的颜色。 　　1. 红黑树数据结构 　　建立在 BST 二叉搜索树的基础上，AVL、2-3树、红黑树都是自平衡二叉树（统称B-树）。但相比于AVL树，高度平衡所带来的时间复杂度，红黑树对平衡的控制要宽松一些，红黑树只需要保证黑色节点平衡即可。也正因红黑树在插入和删除时不需要太多的平衡操作，也让它成为；Java中HashMap的素碰撞后的转换、Linux的CFS进行调度算法、多路复用技术的Epoll等各类底层的数据结构实现。 　　但红黑树并不是一个那么容易理解的知识点，甚至很多资料都只是给出红黑树的理论，但为什么要染色、为什么要左旋、为什么还要左旋接右旋。这样的知识点本就不应该是考死记硬背来学习的，这根本不是学习编程的”套路“。—— 你背的再溜，也没法理解核心本质，忘也只是时间的问题！ 　　其实根据红黑树的历史来看，最早红黑树就是来自于2-3树的结构，所以要学习清楚的结构就要学习 2-3树。但同时对于 2-3树的学习也不能只是依靠一份理论，否则对于红黑的学习来看，就是用不太理解的 2-3树理论套红黑树理论，依旧没法理解。所以小傅哥在上一章专门讲解了 2-3树，并做了具体的代码实现。 　　现在来本章，我们在来看看红黑树与2-3树的关系；红黑树红黑树2-3树一棵标准二叉红黑树红黑树演化（红色节点拉平）最终恢复到2-3树 　　红黑树一棵在2-3树基础上的左倾红黑树，这样就可以把红色节点与对应的父节点拉平，再把两个拉平的节点放到一个节点中。就是我们熟悉的2-3树了。如果你还没有学习过2-3树，最好先看下小傅哥的2-3树，否则你会看的很吃力 　　现在再来看下红黑树的五条定义；每个节点不是红色就是黑色。 黑色决定平衡，红色不决定平衡。这对应了2-3树中一个节点内可以存放1~2个节点。根是黑色的。 这条规则有时会被省略。由于根总是可以从红色变为黑色，但不一定相反，因此该规则对分析几乎没有影响。所有叶子 (NIL) 都是黑色的。 这里指的是红黑树都会有一个空的叶子节点，是红黑树自己的规则。如果一个节点是红色的，那么它的两个子节点都是黑色的。 通常这条规则也叫不会有连续的红色节点。这体现在2-3树中，一个节点最多临时会有3个节点，中间是黑色节点，左右是红色节点。2-3树中出现这样的情况后，会进行节点迁移，中间节点成为父节点，左右节点成为子节点。从给定节点到其任何后代 NIL 节点的每条路径都包含相同数量的黑色节点。 对应2-3树中，每一层都只是有一个节点贡献了树高决定平衡性，也就是对应红黑树中的黑色节点。 　　好啦，现在再看这5条理论是不就不需要再死记硬背了。因为编程本就是对数学逻辑的具体实现，只要把核心逻辑理顺其实很好理解。接下来小傅哥就带着大家动手实现一下红黑树。 　　2. 红黑树结构实现 　　基于 BST 二叉搜索树的基础上，AVL树添加了树高作为计算平衡因子的条件，那么红黑树也需要添加一个新的颜色属性，用于处理平衡操作。 　　相比于AVL树通过左右旋转平衡树高，红黑树则是在2-3树的基础上，只对黑色节点维护树高，所以它会使用到染色和左右旋来对树高调衡。染色与左右旋相比，减少了平衡操作源码地址：https://github.com/fuzhengwei/java-algorithms本章源码：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/tree动画演示：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html—— 红黑树初次理解还是比较困难的，可以结合学习内容的同时做一些动画演示。 　　2.1 左倾染色 　　新增节点1，相当于2-3树中在节点2上添加了一个节点，这个时候并不影响树高，只需要染色保持红黑树的规则即可。染色过程如图所示。

　　染色时根据当前节点的爷爷节点，找到当前节点的叔叔节点。再把父节点染黑、叔叔节点染黑，爷爷节点染红。但爷爷节点染红是临时的，当平衡树高操作后会把根节点染黑。具体参考源码 　　2.2 右倾染色 　　新增节点4，相当于2-3树中在节点3上添加了一个节点，这个时候并不影响树高，只需要染色保持红黑树的规则即可。染色过程如图所示。

　　染色时根据当前节点的爷爷节点，找到当前节点的叔叔节点。再把父节点染黑、叔叔节点染黑，爷爷节点染红。但爷爷节点染红是临时的，当平衡树高操作后会把根节点染黑。具体参考源码 　　2.3 左旋调衡 　　2.3.1 一次左旋 　　对照2-3树，只有当一个节点内有3个节点的时候，才需要调衡。那么红黑树则是判断当前节点的叔叔节点是否为红色节点，如果不是则没法通过染色调衡，也就是需要选择进行调衡。

　　当你把红黑树对照理解成2-3树，如图中第1步骤下的左侧小图，新增的节点5倒置2-3树不平衡。那么这个时候需要把2-3树中节点4提起来，而对应红黑树则需要先进行染色，待操作的节点4为黑色，两个孩子节点为红色。最后是把节点3进行一次左旋操作，完成树的平衡。对应步骤3中的左侧小图是2-3树调衡后的结果。 　　2.3.2 右旋 + 左旋 　　当一次左旋没法调衡，需要右旋+左旋的情况，在AVL树中有同样的场景。本身树需要左旋操作，但整体分支树节点偏左，此时需要右旋调整树结构再左旋。此处可参考小傅哥编写的AVL树

　　红黑树新增节点4以后，4↙5 结构偏左，需要先进行右旋调衡树结构，再进行左旋。其实这个时候再进行的左旋就和上面一次左旋操作一致了。 　　4. 右旋调衡 　　2.4.1 一次右旋 　　对照2-3树，只有当一个节点内有3个节点的时候，才需要调衡。那么红黑树则是判断当前节点的叔叔节点是否为红色节点，如果不是则没法通过染色调衡，也就是需要选择进行调衡。

　　当你把红黑树对照理解成2-3树，如图中第1步骤下的右侧小图，新增的节点1倒置2-3树不平衡。那么这个时候需要把2-3树中节点2提起来，而对应红黑树则需要先进行染色，待操作的节点2为黑色，两个孩子节点为红色。最后是把节点2进行一次右旋操作，完成树的平衡。对应步骤3中的右侧小图是2-3树调衡后的结果。 　　2.4.2 左旋 + 右旋 　　当一次左旋没法调衡，需要左旋+右旋的情况，在AVL树中有同样的场景。本身树需要右旋操作，但整体分支树节点偏右，此时需要左旋调整树结构再右旋。

　　红黑树新增节点2以后，1↘2 结构偏右，需要先进行左旋调衡树结构，再进行右旋。其实这个时候再进行的右旋就和上面一次右旋操作一致了。 　　3. 红黑树实现测试 　　为了验证红黑树的实现正确与否，这里我们做一下随机节点的插入，如果它能一直保持平衡，那么它就是一颗可靠红黑平衡树。 　　测试结果 　　随机插入20个节点，每个节点的顺序已经打印，经过红黑树的染色和左右旋调衡后，二叉结构始终保持树保持平衡，那么验证通过。另外本文出现的案例已经在单测试中都有编写，读者可以在源码中进行测试。