首页 > 代码库 > 马程序员学习笔记——红黑树解析二

马程序员学习笔记——红黑树解析二

---------------------- ASP.Net+Unity开发.Net培训、期待与您交流! ----------------------

四、树中删除元素

1.先找到需要删除的元素。

2.

2.1如果被删元素没有子元素,那么直接用NIL节点代替他;

2.2如果被删元素只有一个子元素,那么直接用这个子元素代替他;

2.3如果被删元素有两个子元素,那么就用左子元素中的最大元素或者子元素的最小元素代替他。

比如说原来要删除的元素是N,N有两个分支,其中P是N分支中的最大元素,那么就把P的值赋给N,然后删除P,这时其实真正删除的是P元素了(而P元素不可能有两儿子,否则的话,就存在比P还要大的元素了,)然后就回到情况2.1或者2.2了。

e.g.:如图9所示,当删除结点20时,实际被删除的结点应该为18,结点20的数据变为18(颜色不变)


3.由于删除了一个元素,所以红黑树的5条特性可能被破坏,这时就需要通过系列的旋转变色来恢复特性。


五、删除修复

先回顾一下红黑树的五条特性:

1.节点只有红色或黑色。

2.根节点是黑色。

3.每个叶子结点都带有两个空的黑色结点(被称为黑哨兵,即NIL节点),如果一个结点n的只有一个左孩子,那么n的右孩子是一个黑哨兵;如果结点n只有一个右孩子,那么n的左孩子是一个黑哨兵。

4.红节点的两儿子都是黑色的,即红节点不相邻。

5.树上任一节点,从该节点到其叶节点的所有路径上都包含相同的黑节点(包括NIL节点)。


OK,现在先回顾一下四.2.3中的那个例子,我们可以得到一下结论:

真正删除的点,必定是只有一个儿子或者没有儿子(NIL节点不算儿子)的点,道理很简单,如果被删除的点有一个黑儿子,那么原树本来就是不平衡的(性质5);如果被删除的点有两个儿子,那他就不是真正被删除的点(参见 四.2.3)。理解这点非常重要


现在分析删除的几种情况:

1.被删除的元素是红色的,那么删除它后,直接用它儿子或NIL节点代替就好,不会破坏任何特性。

2.如果被删除的元素是黑色的,那么删除后,必定会破坏特性5(少了一个黑色嘛)。这时,我们可以使用这样的思想:比如N是被删点,H是要接替N的点;N被删除后,把它自己的黑色强加给了H,同时H又不放弃自己原来的颜色,相当于H一个人拥有了两种元素,这时特性5是不是保持住了呢?

有了这个思想后,我们继续分析:

2.1:接替点颜色是 红+黑(前面那色是自己的,后面那色是父亲那继承的)。

处理方法:直接把接替点颜色变黑就好了(相当于把自己的红色变成父亲的黑色)。

2.2:接替点颜色是 黑+黑,并且删除点是原来的根节点。

处理方法:直接变空树,(这种情况其实原来整个树只有一个元素,就是它自己)。

2.3:接替点颜色是 黑+黑,(除了2.2以外的双黑情况)。

这时最为复杂,我们先看下面这张图(没有方便的画图软件,所以纯手绘了,大家见谅^_^):

下图中蓝色的箭头所指的元素,表示真正要删除的元素;黑色的小方框,表示NIL节点;N表示被删元素,P表示被删元素的父亲,S表示被删元素的兄弟。


上面这张图,对应于2.1(被删点颜色是红+黑)这种情况




这三张图,完整诠释了原始黑+黑的全部情况(10种),但其实这10种情况,可以归纳为

A(一)、B(二、三)、C(四、五)、D(六七八九)、E(十)这五种情况。


下面详细解析(下面电脑图中的X、W和我手绘图中N、S含义是相同的,分部代表被删除的点和它的兄弟点):

情况A:x的兄弟w是红色的(此时父节点P和S的子节点都是黑的,这时因为特性4)


处理方法:B点变红,D点变黑,然后以B点为轴左旋。相当于把右枝的红色移到了左支,但A的兄弟却从红色变成了黑色,使它符合情况B

情况B:X的兄弟W是黑色的,并且W的两儿子也是黑色的


处理方法:因为X和W都是黑色的,所以我们可以将他们的黑色上推(上推的含义参加我上一篇文章)一层,这时D变成了红色,但X因为有双重黑色,所以被推去一层后,还有一层。

这时候会有两种可能,情况我手绘图的二、三。如果是情况二,也就意味着被删点的父亲原来是黑色的,那么它现在变成了双重黑色,然后我们可以以它父亲为新的判定点(new x)来从新处理。

如果是情况三,就是被删点的父亲原来是红色的,那么它现在变成了单重黑色,那么就直接平衡了,OK,完工。

情况C:X的兄弟W是黑色的,W的左儿子是红色的,W的右儿子是黑色的。


处理方法:将W的颜色变成红,它左儿子C变成黑(互换),然后以W为支点进行右旋。使它符合情况D

情况D:X的兄弟W是黑色的,W的右儿子是红色的,W的左儿子颜色随意。


处理方法:将父亲C的颜色给兄弟W,父亲自己变成黑色,W的右儿子也变成黑色。然后以父亲为支点,进行左旋,OK,大功告成。

这个参看我手绘图六七八九更醒目,因为当X被删掉后,左边就少了一个黑节点,这样性质5就被破坏了,为了弥补,把父亲变黑,然后移到左边来。但这样一来,定点的颜色也可能变化,所以就先把父亲的颜色给兄弟W。这样左边和中间都满足了,只剩下右边少了一个黑(兄弟被当成顶点了嘛),正好右边有一个红色(原兄弟W的右儿子),那直接把它变黑,皆大欢喜。

情况E:被删点是根元素,并且整个树就它一个

处理方法:这种情况相当简单,直接变空树。


好了,关于被删点的接替点颜色是黑+黑(2.2,2.3)的处理,通过我手绘图的10种详细情况,归纳出5种普遍情况(其实是4种,情况E实在太简单),到此为止全部剖析完毕。再回顾一下:

红黑树删除的几种情况:

、被删点是红色,那么直接删除,用后续点接替就好了

、被删点是黑色的,那么把它删除,并把它的黑色继承给它的儿子。

这时根据他儿子的双重颜色,有可以分为:

2.1:它儿子是红+黑,那么直接变黑,over。

2.2:它儿子是黑+黑,又可分为5种:

2.2.A:x的兄弟w是红色的。

2.2.B:x的兄弟w是黑色的,且w的俩个孩子都是黑色的。

2.2.C:x的兄弟w是黑色的,w的左孩子是红色,w的右孩子是黑色。

2.2.D:x的兄弟w是黑色的,且w的右孩子时红色的。

2.2.E:被删点是根元素,并且整个树就它一个。

note:以上对节点的删除,都是考虑的被删节点是父节点的左节点的情况,如是右节点,思路相同,操作相反


结语:只要牢牢抓住红黑树的5个性质不放,无论是插入还是删除,左旋还是右旋,目的只有一个——都只为了保持和修复红黑树的5个性质而已。



---------------------- ASP.Net+Unity开发.Net培训、期待与您交流! ----------------------详细请查看:http://edu.csdn.net