写点什么

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

用户头像
小松漫步
关注
发布于: 2020 年 10 月 14 日

前言



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



是的



自从小松拿到了公司的测试机,近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-,虽然其本质是二三树,插入规则本质也是二三树的插入规则,但是还是需要一些变化



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



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



发布于: 2020 年 10 月 14 日阅读数: 41
用户头像

小松漫步

关注

公众号【小松漫步】,累过哭过,依然坚持 2018.12.12 加入

98年刚入职鹅厂的程序员

评论

发布
暂无评论
「红黑树」背了又忘?深入本质,他也不过是一棵二叉树