全部博文(89)
分类: C/C++
2013-12-02 18:34:57
引言:
再次,重述下红黑树的五个性质:
一般的,红黑树,满足以下性质,即只有满足以下性质的树,我们才称之为红黑树:
1)每个结点要么是红的,要么是黑的。
2)根结点是黑的。
3)每个叶结点,即空结点(NIL)是黑的。
4)如果一个结点是红的,那么它的两个儿子都是黑的。
5)对每个结点,从该结点到期子孙结点的所有路径上包含相同数目的黑结点。
一、左旋与右旋
先明确一点:为什么要左旋?
因为红黑树插入或删除结点后,树的结构发生了变化,从而可能会破坏红黑树的性质。
为了维持插入、或删除结点后的树,仍然是一棵红黑树,所以有必要对树的结构做部分调整,从而恢复红黑树的原本性质。
而为了恢复红黑性质而做的动作包括:
结点颜色的改变(重新着色),和结点的调整。
这部分结点的调整工作,改变指针结构,即是通过左旋或右旋而达到目的。
从而使插入、或删除结点的树重新成为一颗新的红黑树。
ok,请看下图:
再次,着重分析左旋算法:
左旋,如图所示(左->右),以x->y之间的链为“支轴”进行,
使y成为该新子树的根,x成为y的左孩子,而y的左孩子成为x的右孩子
算法很简单,还要注意一点,各个结点从左往右,不论是左旋前还是左旋后,结点大小都是从小到大。
左旋代码实现,分三步(注意我给的注释)
The pseudocode for LEFT-ROTATE assumes that right[x] != nil[T] and that the root's parent is nil[T].
//这段左旋代码,原书第一版英文版与第二版中文版,有所出入。
//个人觉得,第二版更精准。所以,此段代码以第二版中文版为准。
左旋、右旋都是对称的,且都是在O(1)时间内完成。因为旋转时只有指针被改变,而结点中的所有域都保持不变。
二、左旋的一个实例
不作过多介绍,看下副图,一目了然。
LEFT-ROTATE(T,x)的操作过程
提醒:看下文之前,请首先务必明确却别以下两种操作:
1.红黑树插入、删除结点的操作
//如插入中, 红黑树插入结点操作:RB-INSERT(T,z)。
2.红黑树已经插入、删除结点之后:
为了保证红黑树原有的红黑性质而坐的回复与保持红黑性质的操作。
//如插入中,为了恢复和保持原有红黑性质,所做的工作:RB-INSERT-FIXUP(T, z)。
ok,请继续。
三、红黑树的插入算法实现
RB-INSERT(T, z) //注意我给的注释。。。
还记得,我开头说的那句话么。
是的,时刻记住,不论是左旋还是右旋,不论是插入、还是删除,都要记得恢复和保持红黑树的5个性质。
四、调用RB-INSERT-FIXUP(T,z)来保持红黑树的性质
//
//这幅图有个小小的问题,读者可能会产生误解。图中左侧所表明的情况2、情况3所标的位置都要标上一点。
//请以途中的表明的case1、case2、case3为准。
六、红黑树插入的第一种情况(RB-INSERT-FIXUP(T,z)代码的具体分析一)
为了保证阐述清晰,重述下RB-INSERT-FIXUP(T,z)的源码:
插入的情况1,z的叔叔y是红色的。
第一种情况
如上图所示,a:z为右孩子,b:z为左孩子。
只有p[z]和y都是红色的时候,才会执行此情况1
咱们分析下上图的a情况,即z为右孩子时
因为p[p[z]],即c是黑色,所以将p[z]、y都着为黑色(如上图a部分的右边),
此举解决z、p[z]都是红色的问题,将p[p[z]]着为红色,即保持了性质5.
七、红黑树插入的第二种、第三种情况
插入情况2:z的叔叔y是黑色的,且z是右孩子
插入情况3:z的叔叔y是黑色的,且z是左孩子
这两种情况,是通过z是p[z]的左孩子,还是右孩子区别的。
参照上图,针对情况2,z是它父亲的右孩子,则为了保持红黑性质,左旋则变为情况3,此时z为左孩子,
因为z、p[z]都为黑色,座椅不违反红黑性只(注,情况3中,z的叔叔y是黑色的,否则此种情况就变成上述情况1了)。
ok,我们已经看出来了,情况2,情况3都违反性质4(一个红结点的两个儿子都是黑色的)。
所以情况2->左旋后->情况3,此时情况3同样违反性质4,所以情况3->右旋,得到上图的最后那部分。
注,情况2、3都只违反性质4,其他的性质1235都不违背。
八、接下俩,进入红黑树的删除部分。
九、红黑树删除之4种情况,RB-DELETE-FIXUP(T,x)之代码
在下文的红黑树删除的4种情况,详细、具体分析了上段代码。
十、红黑树删除的4种情况
情况1:x的兄弟w是红色。
情况2:x的兄弟w是黑色的,且w的俩个孩子都是黑色的。
情况3:x的兄弟w是黑色的,w的左孩子时红色,w的右孩子是黑色。
情况4:x的兄弟w是黑色的,且w的右孩子是红色的。
操作流程图。
针对情况1:x的兄弟w是红色的。
对策:改变w、p[x]颜色,再对p[x]做一次左旋,红黑性质得以继续保持。
x的新兄弟new w是旋转之前w的某个孩子,为黑色。
所以,情况1转化成情况2或3、4。
针对情况2:x的兄弟w是黑色,且w的两个孩子都是黑色。
如图所示,w的两个孩子都是黑色,
对策:因为w也是黑色,所以x和w中得去掉一黑色,最后,w变为红色。
p[x]为新结点x,赋给x,x<-p[x]。
针对情况3:x的兄弟w是黑色的,w的左孩子时红色,w的右孩子是黑色。
w为黑,其左孩子为红,右孩子为黑
对策:交换w和其左孩子left[w]的颜色。即上图的D、C颜色互换。
并对w进行右旋,而红黑性质仍然得以保持。
现在x的新兄弟w是一个有红色右孩子的黑结点,于是将情况3转化为情况4.
针对情况4:x的兄弟w是黑色的,且w的右孩子是红色的。
x的兄弟w为黑色,且w的右孩子为红色。
对策:做颜色修改,并对p[x]做一次旋转,可以去掉x的额外黑色,来把x变成单独的黑色,此举不破坏红黑性质。
将x置为根后,循环结束。