试一下说明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完啦~~~。