Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3835841
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8584
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-17 13:52
个人简介

个人微薄: weibo.com/manuscola

文章分类

全部博文(146)

文章存档

2016年(3)

2015年(2)

2014年(5)

2013年(42)

2012年(31)

2011年(58)

2010年(5)

分类:

2011-06-04 20:18:27

一 红黑树的删除节点
第一步删除节点,先找到需要删除的节点
void rb_erase(struct rb_node *node, struct rb_root *root)
1  左孩子为空,右孩子为空
 则 直接删除这个节点。child = NULL, parent为 node的parent。
 如果node is black ,需要调用调整函数__rb_erase_color(child, parent, root);

2 左孩子 为空,右孩子不为空,
  删除的节点为node,child = node->right,parent = node->parent。
  如果node is black ,需要调用调整函数 __rb_erase_color(child, parent, root);

3 左孩子存在,右孩子为空
  删除节点为node, child = node->left,parent = node->parent;
  如果node is black  调用 调整函数__rb_erase_color(child, parent, root);

4 左孩子不为空,右孩子也不为空
 右孩子存在,则寻找node的后继,即寻找右孩子为根的具有最小key的节点。换言之寻找 左孩子的左孩子的左孩子,直到,没有左孩子节点为止。
 
               node = node->rb_right;
while ((left = node->rb_left) != NULL)
node = left;
child = node->rb_right; 
node 为入参node的后继, child 为 找到的后继的右孩子(可能为NULL)。

情况1  入参node的右孩子有左孩子
 首先用old 保存要删除的node参数,然后去查找node的后继
 因为node 的右孩子有左孩子,所以一直去找左孩子,直到找到没有左孩子的节点,
将这个节点记为 node ,node的父亲记为parent ,node->right = child(可能为NULL)

其实表面上看 我们删除的是old 这个节点,实际上我们删除的是node的这个节点,我们看一下,
删除之后的效果就可以理解, old被删除了,但是node填充old 的位置。 node 被摘走了,
node 没有左孩子只有右孩子,右孩子就交给parent领养。即child的父亲变成了parent,
parent的左孩子变成了child。


情况2  入参node 的右孩子没有左孩子

入参node的右孩子没有左孩子,所以node的右孩子就是入参node的后继。
表面上看,要删除的是入参node 即old,但是,后继node继承了old的位置,
所以删除的是后继。后继node的右孩子child 现在父亲仍然是后继。

现在 child = 后继的右孩子(可能为空)
    parent = 入参node的右孩子 ,即后继
    如果 入参的node的右孩子为black,那么
    将child parent 作为参数传入 调整函数__rb_erase_color(child, parent, root);


二  为什么需要调整
前面说了,表面上看,删除的是入参,其实删除的是入参node的后继。
因为入参node 的后继完全取代了入参node的位置,并且颜色也是入参node的颜色。
换言之,表面上看 入参node被删,其实不过是node的key 和value发生了变化。
相反,入参的后继 ,被放入到入参的位置,自己原来的位置无人顶替(这么说也不严格正确,实际上后继
的右孩子即child顶替了自己)。相当于入参node 的后继被删除。

为啥入参node的后继被删就有可能破坏 红黑树的属性呢?
考虑下红黑树的第五条性质, 各个支路black的个数必须一致。
如果 删掉一个黑色的node,对黑色node 所在的分支,必然比其他分支少一个黑节点,
这就是删除之后,需要调整的根源。

所有的调整以node 是父亲的左孩子为例,右孩子的情况对称可得。

1) 如果实际删掉的后继 为root,并且 child 顶替了自己的位置,成为了新的root,
那么必须将 root 颜色变成black。

2)如果child 为红色,那就好办了,因为有个node 是black 被删掉了,他们的支路少个black,
  既然child 是红色的,那就直接将child 改成黑色,万事OK

3) child 是black  这种情况就惨了,非常惨。下面分析这种情况

三  函数 __rb_erase_color

static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
    struct rb_root *root)

我们知道调整的时候,是把child  parent 传入__rb_erase_color。
所以这个函数的node 就是前面将的 child, parent 就是前面得parent。

node所在的支路和其他支路比缺少一个black,只是我们需铭记在心的。
1)  node 的兄弟 brother是黑,brother的两个孩子也是黑。
这种情况最好,既然兄弟brother 分支 多一个black, 而且 brother 的两个儿子也是black,
那太好了,直接将brother 调成red。 现在由于node的兄弟brother比较大度,自己去掉了一个black,node 和他的兄弟 黑色的个数一致了,但是,世界很大,如果node的父亲是根,OK,一切都很公平了,但是如果node 的父亲不是根,node 父亲这一脉,其实比node叔父这一脉 少一个黑色节点。

所以 node = node->parent ,继续迭代。



2)brother 是黑,右孩子是红色。
如果兄弟是黑色,右孩子是红色,
brother 继承父亲颜色,父亲变成黑色, brother的右孩子变黑, 以父亲为轴左旋

rb_set_color(brother, rb_color(parent));
rb_set_black(parent);
if (brother->rb_right)
rb_set_black(other->rb_right);
__rb_rotate_left(parent, root);

node = root->rb_node;
break;
通过这些操作,兄弟这一支 黑色的个数并没有减少,但是node 坐在的这一支,因为将父亲变成了黑色,
增加一个black,所以,天下太平了。

3)brother 是黑色,左孩子是红色 ,右孩子是黑色;
  这种情况经过变化可以变成前面分析的情况2)
  办法是 :
   将brother 的左孩子变黑,brother变红,以brother为轴 右旋。
if (!brother->rb_right || rb_is_black(brother->rb_right))
{
struct rb_node *o_left;
if ((o_left = brother->rb_left))
rb_set_black(o_left);
rb_set_red(brother);
__rb_rotate_right(brother, root);
brother = parent->rb_right;
}


4) 第四种情况是最悲惨的情况
node 的兄弟干脆是red。
这种情况需要转化成 node的兄弟brother 变成black,就能使用前面的办法了。
转化方法如下:

如果C的两个孩子为黑色,那么,我们就转成了第一种情况。brother 是black。brother的两个儿子是black。
这种情况下,因为parent 是red,所以下一轮循环,只需要将parent 从red 变成black ,自己父亲这一支就再也不缺少一个black,从而天下太平。

                        if (rb_is_red(brother))
{
rb_set_black(brother);
rb_set_red(parent);
__rb_rotate_left(parent, root);
brother = parent->rb_right;
}

阅读(6975) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~