`

试一下说明RB-Delete-Fixed .

阅读更多
Red-Black-Tree又叫红黑树,各操作都为O(logn)因为加入左特殊ge规则,最大高度可以控制到2*logn且最长路径最大为最短路径ge2倍。个人认为,系一种剩适合练习但唔系好实用ge结构,因为好复杂,但系又系好多树ge基础数据结构窝,所以就睇下咯。



首先介绍距ge5种性质:

1)每个结点系红色或者黑色。

2)根必须系黑色。

3)每个叶结点必为黑色。

4)红色结点必有两个黑色儿子。(保证无两个红色节点相连)

5)从树中每个节点开始到其所有叶子所经过ge黑结点个数相同。

(因为性质4,所以最坏情况就系两个黑结点之间都有一个红结点,所以最长路径为最短路径两倍)



跟住就说明下RB-Delete-Fixed(删除操作后恢复红黑性质)咯,以下内容十分似扭魔方,哈哈。



以下情况只系删除结点y为黑色ge时候发生,考察儿子x,且被删结点y最多只有一个儿子(自己查下基本二叉树删除操作啦哈哈)。



首先假设x系当前结点指针,且为y左儿子(右儿子操作对称),w系x兄弟ge指针,p[x]系x老豆ge指针,呢个操作首先系假设x有多一重黑色,既将被删黑色结点ge黑色往下推,使其保证性质5,但系破坏左性质1(前提),因为根据假设,x结点系红黑或者双重黑色,以下证明操作回复红黑性质1,2,4,5,唔洗理3,因为红黑树用左哨兵。{= =}



定义x所指向结点多一层黑色(假设ge黑色,最后镀系边个点吾一定),并不是x本身color属性变化(color属性只有红色或黑色)。



情况1)xcolor属性系红色。



一、x系根部,只有可能破坏性质性质2,只需要直接镀上黑色就回复左。



二、x唔系根部,无破坏性质2,有可能破坏性质4(p[x]有可能红色),只需直接将黑色镀上,回复性质1,4,5。



情况2)xcolor属性系黑色,考察其兄弟w。



一、w为红色(即p[x]color必为黑色)

将p[x]color改为红色,w改为黑色,对p[x]做左旋后,w变为p[x]父结点,

w左儿子变成x兄弟,且必定为黑色(因为w本来红色),无破坏性质,2,3,4,5,未回复性质1.进入下一次循环,(注意此时p[x]为红色,新w为黑色。)



二、w为黑色(因为性质4,通常系红色,除左p[x]系根)



小情况1)w两个儿子都为黑色。

注意x同埋w都系黑色,只需要将黑色往p[x]推就ok啦。即将wcolor改为红色,x指针指向p[x],尼几个操作无破坏2,3,4,5。呢个时候有两种情况:

1、p[x]本来color为红色,将x指针黑色镀上后,就可以回复性质1,循环结束。

(注意到如果从“一”进入到呢种情况,循环必定结束)

2、p[x]本来color为黑色,吾可以将黑色镀上,因为宜家p[x]系双重黑色,未回复性质1,继续下一次循环。



小情况2)w左儿子为红色,右儿子为黑色。

将w左儿子着黑色,w着色红色,w做右旋,新w为原w左儿子,等价于原w左子树少一红结点,右子树多一红结点,不破坏性质2,3,4,5。未回复性质1,继续下一次循环。



小情况3)w右儿子为红色。

将w着色为红色,p[x]同w右儿子着色为黑色,对p[x]做左旋后,x可以吾捞,因为已经回复左性质1。其他红黑属性无被破坏。



9up完啦~~~。
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics