「红黑树」背了又忘?深入本质,他也不过是一棵二叉树
前言
小松最近好久没有更新文章了,是小松懒了吗?
是的
自从小松拿到了公司的测试机,近5000的小米10 Pro,还有因为内推几十个人得到的airpods pro奖品,还有公司每月发的Q币和点券,于是我的周末变成了这样。
早上10点来公司,信心满满准备好好学一天,看到小米10,心想,要不玩一把王者?
公司的网还贼好,下载近5~6m/s,开局全程50延迟以下,然后打开mac,上爱奇艺播放4k杜比漫威大片,在28寸大屏下当背景音,带上airpods,世界只剩我一人,吹着空调,喝着咖啡,动动手指就买了以前就很喜欢的英雄和皮肤(我玩王者几千把了,从来没充过钱)。
于是瞬间中午了……
下午,头晕晕的,学又学不了,写也写不了,不如看b站吧!
二叉树
好了,闲话不多说,以下内容将会建立从二叉树到红黑树的演变过程,掌握这一过程,就不会再忘了,全程请每一个步骤都弄明白。
首先,我们为什么要建立二叉树?
我想答案大同小异,就是增加增删查改的速度。
如果说,一棵树只有左子节点,那么他将和链表没有区别,所以,构建一棵好的二叉树,节点间的平衡是我们要考虑的头等大事,与之对应的,平衡二叉树得到了广泛应用。
现在我们定义一个平衡操作:每增加一个节点,树就自动进行平衡,变成平衡二叉树。
但是实际上,如果每次增加一个节点都要进行平衡操作,显然消耗比较大。
二三树
为了减少这种消耗,所以现在我们考虑设置”二-三树“。
如上图所示,增加一个可以连接三个子节点的节点,而这个节点本身,由两个节点组合而成,也就是说,他可以分裂成两个节点,比如上面的EJ,AC,SX。
单键值节点简称为2-,双键值节点简称为3-。
现在我们有了一棵新的树,我们该干嘛?无脑增删改查。
查找
判断一个键是否在树中,只需要和从根节点开始,小则往左,大则往右,如果进入到两个键值的节点,照样可以比较。
插入
对于普通二叉树而言,插入一个新节点挂在底部是无法保证平衡的,只有特殊的二叉平衡树可以,但是,一棵普通的二三树,就可以完成平衡,分为四(liang)种情况:
插入到2-的节点中
这种情况,不可能破坏平衡
插入到3-节点中(只含有一个3-节点)
插入到3-节点中(父节点为2-)
插入到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?答案是不行,因为红链接必须是左链接,原因?在后文中将旋转会解释
还记得红黑树的性质吗?那些背了就忘的性质
所有空链到根节点经历的黑链数量相同
没有任何一个结点同时和两条红链接相连
虽然我们画的时候是链接红色,但是真实编码的时候,显然,我们是在节点中设置,比如
小结
红黑树由于没有3-,虽然其本质是二三树,插入规则本质也是二三树的插入规则,但是还是需要一些变化
此时要涉及到更多内容,诸如颜色变换,旋转,等等,限于篇幅,此文是做为红黑树来源的探讨,红黑树所有的性质都是在用二叉树的形式来完成二三树的规则,关于二三树在进行“二叉化”,并改名为红黑树的过程中,他设置了哪些规则,我们下文再聊咯
本文参考自《算法》第四版
版权声明: 本文为 InfoQ 作者【小松漫步】的原创文章。
原文链接:【http://xie.infoq.cn/article/f0caa1e1cecfdc783fdd82f58】。文章转载请联系作者。
评论