「红黑树」背了又忘？深入本质，他也不过是一棵二叉树

前言



小松最近好久没有更新文章了，是小松懒了吗？



是的



自从小松拿到了公司的测试机，近5000的小米10 Pro，还有因为内推几十个人得到的airpods pro奖品，还有公司每月发的Q币和点券，于是我的周末变成了这样。



早上10点来公司，信心满满准备好好学一天，看到小米10，心想，要不玩一把王者？



公司的网还贼好，下载近5~6m/s，开局全程50延迟以下，然后打开mac，上爱奇艺播放4k杜比漫威大片，在28寸大屏下当背景音，带上airpods，世界只剩我一人，吹着空调，喝着咖啡，动动手指就买了以前就很喜欢的英雄和皮肤（我玩王者几千把了，从来没充过钱）。



于是瞬间中午了……



下午，头晕晕的，学又学不了，写也写不了，不如看b站吧！



二叉树



好了，闲话不多说，以下内容将会建立从二叉树到红黑树的演变过程，掌握这一过程，就不会再忘了，全程请每一个步骤都弄明白。



首先，我们为什么要建立二叉树？



我想答案大同小异，就是增加增删查改的速度。



如果说，一棵树只有左子节点，那么他将和链表没有区别，所以，构建一棵好的二叉树，节点间的平衡是我们要考虑的头等大事，与之对应的，平衡二叉树得到了广泛应用。



现在我们定义一个平衡操作：每增加一个节点，树就自动进行平衡，变成平衡二叉树。



但是实际上，如果每次增加一个节点都要进行平衡操作，显然消耗比较大。



二三树



为了减少这种消耗，所以现在我们考虑设置”二-三树“。





如上图所示，增加一个可以连接三个子节点的节点，而这个节点本身，由两个节点组合而成，也就是说，他可以分裂成两个节点，比如上面的EJ，AC，SX。



单键值节点简称为2-，双键值节点简称为3-。



现在我们有了一棵新的树，我们该干嘛？无脑增删改查。



查找



判断一个键是否在树中，只需要和从根节点开始，小则往左，大则往右，如果进入到两个键值的节点，照样可以比较。





插入



对于普通二叉树而言，插入一个新节点挂在底部是无法保证平衡的，只有特殊的二叉平衡树可以，但是，一棵普通的二三树，就可以完成平衡，分为四（liang）种情况：



1. 插入到2-的节点中





这种情况，不可能破坏平衡



1. 插入到3-节点中（只含有一个3-节点）



1. 插入到3-节点中（父节点为2-）



1. 插入到3-节点（父节点为3-）





以上四种情况都是插入的规则，看似很多，其实很简单，第1条就是简单的合入，第2~4条都是针对插入到3-节点下的情况分析，思路就是：



多则分裂子节点，少则合入父节点。



必不可少的是出现4-节点，这个处理根据父节点和大小不同有1+2+3=6种情况。





在完成了上面的插入之后，你会发现，我们并没有对左右节点区别对待，要么就不生成子节点，要么同时生成左右子节点，所以，二三树从原理上，只要他原来是平衡的，那插入后就一定是平衡的。



二三树生长过程



还记得二叉树是如何生长的吗？有一个根节点，然后自上而下的挂节点，这样的树一不小心就会很丑陋，而二三树呢？是自下而上的，如何往上？分裂后键值大小居中的往上。





为什么我要用丑陋来形容二叉树插入？因为我去年在学《编译原理》时，我们老师就对比过自上而下的LL分析法，和自下而上的LR分析法，他对前者的评价就是”丑陋“。



对比二叉树而二三树，事实上，跳脱出计算机，只要涉及到决策过程都会用到树，而用到树，一定能分自上而下构建和自下而上构建，这种思想是贯通在每一个领域的，大道至简，需要我辈慢慢参悟。



红黑树



你可能快忘了，本文的目标是红黑树，结果我却说了半天的二三树？



这是我在张冠李戴？当然不是，实际上



红黑树就是将二三树进行”二叉化“



换句话说，就是有二叉树的形式，同时具备二三树的精髓



为什么要这样？因为二三树虽好，但是实现起来毕竟复杂，各种2-节点，3-节点，4-节点容易错，必须统一为2-节点



节点变成2-节点，也就是说，所有3-节点都要被拆成2-节点，而且我们要想办法记录这一信息。



什么方法？就是节点间的链接方式变成了红色和黑色



黑色自然是普通链接，红色是什么？



红色是羁绊，红色是姻缘，红色，



是那个被我们残忍拆开的3-节点之间的联系





上图中的二三树ab节点，转换为红黑树之后，ab就会以红色链接，然后他们的子节点分配，你可能好奇是否可以a做根节点？又子节点为b？答案是不行，因为红链接必须是左链接，原因？在后文中将旋转会解释



还记得红黑树的性质吗？那些背了就忘的性质



1. 所有空链到根节点经历的黑链数量相同



1. 

2. 没有任何一个结点同时和两条红链接相连



虽然我们画的时候是链接红色，但是真实编码的时候，显然，我们是在节点中设置，比如





小结



红黑树由于没有3-，虽然其本质是二三树，插入规则本质也是二三树的插入规则，但是还是需要一些变化



此时要涉及到更多内容，诸如颜色变换，旋转，等等，限于篇幅，此文是做为红黑树来源的探讨，红黑树所有的性质都是在用二叉树的形式来完成二三树的规则，关于二三树在进行“二叉化”，并改名为红黑树的过程中，他设置了哪些规则，我们下文再聊咯



本文参考自《算法》第四版