雅乐网

计算机技术、学习成长

计算机 » 数据结构 » 从B-树角度理解红黑树背后的原理

从B-树角度理解红黑树背后的原理

红黑树也是一种平衡二叉树,但并不像AVL那样严格。红黑树有一些等价的表述,其中比较流行的就是给结点染上红色或黑色。下面是一棵红黑树。

红黑树,来自维基百科

一棵红黑树示例,图片来自维基百科

红黑树满足4条性质:

1. 根结点是黑色的(如果不是空树)

2. 外部结点是黑色的(外部结点是把NULL指针看做指向一个代表NULL的结点)

3. 红色结点只能有黑色的孩子(从树根到外部结点路径上不会有连续的红结点)

4. 外部结点到树根的路径中包含相同数目的黑色结点。

红黑树 = 4阶B-树

红黑树的4个性质

先来分析红黑树的性质。

性质1:树根为黑色。

性质2:外部结点是黑色的。

看性质3:红色结点只有黑色孩子。即从根到叶路径中不会有连续的2个红结点。

性质3的逆否命题是:如果一个结点是红色结点,它不会有红色父亲。那么它只可能有黑色父亲,结合性质1:树根为黑,有红结点必有父亲。所以,红结点必有黑色父亲

性质4:外部结点到树根的路径中包含相同数目的黑色结点。这也叫做红黑树的黑高度。这可以让人想到B-树,B-树的叶节点都在同一层次。如果只看黑结点,这和B-树非常符合。

B树的超级节点

再回忆一下B-树的超级节点

scrn20160117111953

通过上面性质的分析,红色结点必有黑父亲,而每条路径中黑结点数目一致。如果把所有的红结点都和它的黑父亲结合,形成超级结点,就得到了所有叶结点深度一致的B-树。所有情况一共4种:

1. 左右孩子都为黑 这时候没有红孩子可以提升 超级节点只有黑色结点

scrn20160122132345

2. 左孩子为红

scrn20160122132401

3. 右孩子为红

scrn20160122132415

4. 左右孩子都为红

scrn20160122132428

下面是一个示例

scrn20160122133706

可以看出转换后的超级结点,最多3个元素,其中黑结点在中间,红结点在两边。

也有可能一个黑结点一个红结点,或者只有一个黑结点。

最少有1个结点,2个分支;最多3个结点,4个分支,这正好就是4阶B-树。

高度

由于B树高度为O(logn),红黑树最多也只是对应B树的2倍,因此其高度也是O(logn)。

红黑树的平衡也可以这样看:从根节点到外部结点的路径中黑结点数目相等。而红结点不能连续,最多也只是与黑结点相同,所以不同的路径结点个数不会相差很多。

插入

插入时先按照一般搜索二叉树的方法,插入元素作为叶子,并设置为红色。

插入的新结点记为x ,它的父节点记为p ,它的祖父结点记为g,祖父节点的另一个孩子节点记为u(Uncle)。

从拓扑结构来说,g、p、x的连接有4种情况:左左,左右,右左,右右。

n

右右、右左 可以看做 左左、左右的对称情况,因此下面分析左左和左右情况。

但是修复双红缺陷时,却是从颜色来考虑的。

1. p黑

当插入结点的父节点p是黑结点时,由于新插入x为红色,红黑树的4条性质均未破坏

当p为红色时,由于出现了连续的红结点,红黑树的性质不再满足,这称为双红缺陷。

此时根据黑结点的另一个结点u是红或黑,可以分为2种情况(关系到对应B-树超级结点是否上溢):

2.1 p红u黑

此时提升变换后的B树超级结点个数满足要求,只是顺序不是红黑红,在B-树看来只需要改变颜色即可。还原后,红黑树的拓扑结构和颜色都会发生变化。

scrn20160122191507

下面再给出左右的例子:

zy

因此,这种情况不管拓扑结构是4种中的哪种,只需要把x p g按中序遍历顺序,把4个子树也按照中序遍历顺序,用3+4重构的方法连接起来即可。

2.2 p红u红

这种情况合并超级结点后有4个结点,5个分支,B-树发生上溢。

scrn20160122201902

和上一个情况相反,这里B树发送了拓扑变化(分裂),但对应红黑树只是改变了颜色,拓扑结构没有变化。

g结点变为红色以后,相当于g的父节点插入了一个红结点,这时g的父节点再次面临与 p结点插入后出现的问题相同的问题,这相当于把问题节点p提高了2层。这种问题有时可以一直持续到树根。

下面是左右结构

scrn20160123092151

删除

先使用二叉搜索树的 removeAt(x) 来删除x,并得到x的替代结点r 。

回忆一下removeAt(x)函数面临的3种情况:

x没有左孩子时,用右孩子r代替x

x没有右孩子时,用左孩子r代替x

x既有左孩子,又有右孩子,则取x的中序后继r=succ(x),交换x和r的值,再删除r。r又可以看做要删的x 。这时x没有左孩子,用右孩子r代替x。

之后,removeAt函数返回实际被删除结点的替代者,_hot指向其父亲结点。

不管哪种情况,在删除时,x由它的一个孩子r代替,而另一个孩子(记为w)为空。

scrn20160125102025

删除后,红黑树的性质1和2仍然满足,但3和4就不一定了。这要取决于x和r的颜色。

当x和r有一个是红结点时,T1和T2的相对于x的黑深度原先是1,之后我们只要把r染为黑色,就可以保持黑深度不变,从而红黑树的性质得以满足。

当x和r都是黑色的时候,删除x导致T4黑高度降低,我们称出现了双黑缺陷。此时考虑x的父节点p,x的兄弟节点s ,以及s的某个孩子t。

scrn20160125115143

之所以考虑这些节点的颜色,是和B树删除时下溢的 情况类似的:

要删除结点x,则B-树中超级节点x发生下溢。而s如果为黑,则x有兄弟结点;若s有一个t为红,则s超级节点至少2个结点,可以借出;若s的孩子都为黑,则s不可以借出。若s为红,对应其他情况。

1. s为黑,t为红

scrn20160125121126

结果是t、s、p和T1、T2、T3、T4进行了一次3+4重构。若t,s,p按照中序顺序命名为a,b,c,则a、c染黑,s为原先p的颜色。

2. s为黑 s的两个孩子均为黑

这时候s只有一个结点,不可以借给x删除后的结点,此时需要合并。要从p所属的超级节点中拿出一个作为粘合剂。

scrn20160125124755

这时要讨论p的颜色。如果p是红色,则p所在的超级节点有多余1个结点,合并后下溢不会上升。如果p为黑色,p所在超级节点只有1个结点,会导致下溢向上传播。

2.1 s为黑 s的两个孩子均为黑 p为红

scrn20160125125557

由于p是红色,p的左右至少1个黑色结点,因此p下降后,原先p所在的结点不会继续下溢。

2.2 s为黑 s的两个孩子均为黑 p为黑

这种情况基本步骤和2.1相同,只不过完成后p所在节点会继续下溢。这可以看做p结点的父节点被删除。

scrn20160125130545

 3. s为红

这时的思路是转化为前两种情况

scrn20160125133054

进行旋转后,x的兄弟结点t是黑色,故可以转入上两种情况。因p为红色,故不会转入2.2

总结

参考资料

数据结构(C++语言版)(第3版)/邓俊辉

 

如果文章对你有帮助,欢迎点赞或打赏(金额不限)。你的打赏将全部用于支付网站服务器费用和提高网站文章质量,谢谢支持。

版权声明:

本文由 原创,商业转载请联系作者获得授权。
非商业转载请注明作者 雅乐网 ,并附带本文链接:
http://www.yalewoo.com/red_black_tree_a_b-tree_view.html

上一篇:

下一篇:

我要评论

验证码*: 3 + 8 =