Chinaunix首页 | 论坛 | 博客
  • 博客访问: 458799
  • 博文数量: 72
  • 博客积分: 1851
  • 博客等级: 上尉
  • 技术积分: 1464
  • 用 户 组: 普通用户
  • 注册时间: 2010-09-16 17:50
文章分类

全部博文(72)

文章存档

2013年(1)

2012年(17)

2011年(51)

2010年(3)

分类: C/C++

2011-08-22 00:15:41

红黑树的删除

红黑树的删除远比插入要复杂的多,还是基于算法导论上面进行分析,如普通二叉搜索树一样,需要先将其从二叉树中删除,然后在进行颜色调整,以满足上面的五条性质。

在删除过程中,需要分为四种情况进行考虑:

1.             只有左孩子存在

2.             只有右孩子存在

3.             两孩子均存在

4.             两孩子均不存在

如果为前两种情形时,只需将其对应的孩子的父节点指向其父节点的双亲,如果是第三种情况,则需要去查找该节点的后继节点,然后利用后继节点来进行替换该节点,第四种情况最简单,直接将该节点对应父节点的孩子置为空。

首先下面是普通的删除源码

 

  1. int rb_tree_erase(struct rb_root *root,struct rb_node *node)

  2. {

  3. struct rb_node *child,*parent;

  4.        int color;

  5.        //如果左子树为空,则直接将右子树接上代替该节点

  6.        if(!node->left)

  7.               child = node->right;

  8.        //同理如果右子树为空,则直接将左子树接上以代替该节点

  9.        else if(!node->right)

  10.               child = node->left;

  11.        //否则寻找后继节点

  12.        else

  13.        {

  14.               struct rb_node *old = node,*left;

  15.               //该节点的后继就是右孩子中最左边的节点,中序遍历

  16.               node = node->right;

  17.               while((left = node->left) != NULL)

  18.                      node = left;//该节点最多只留下右孩子节点,无左孩子

  19.               child = node->right;//指向右孩子来修改双亲节点

  20.               parent = node->parent;//父节点修改孩子

  21.               color = node->color;

  22.               //如果孩子存在就修改其双亲节点

  23.               if(child) child->parent = parent;

  24.               if(parent == old) {//如果只有一层,则直接修改右孩子

  25.                      parent->right = child;

  26.                      parent = node;

  27.               } else

  28.                      parent->left = child;//如果node有至少两层的话,更换后继节点

  29.               //直接利用后继进行替换

  30.               node->parent = old->parent;

  31.               node->color = old->color;

  32.               node->right = old->right;

  33.               node->left = old->left;

  34.               //修改双亲节点

  35.               if(old->parent)

  36.               {

  37.                      if(old->parent->left == old)

  38.                             old->parent->left = node;

  39.                      else old->parent->right = node;

  40.               } else

  41.                      root->root = node;

  42.               //old节点被替换,其左孩子的双亲节点也需要修改

  43.               old->left->parent = node;

  44.               //右孩子也需要修改,但是上面可能被替换为空

  45.               if(old->right)

  46.                      old->right->parent = node;

  47.               goto color;

  48.        }

  49.        //修改替换后的双亲节点,前两种情况需要进行此操作,而第三种情况已经进行了处理

  50.        parent = node->parent;

  51.        color = node->color;



  52.        if(child)

  53.               child->parent = parent;

  54.        if(parent)

  55.        {

  56.               if(parent->left == node)

  57.                      parent->left = child;

  58.               else parent->right = child;

  59.        } else

  60.               root->root = child;

  61. color://如果后继节点为黑色,需要进行颜色调整

  62.        if(color == BLACK)

  63.               __rb_tree_erase_fixup(root,parent,child);

  64.        root->len --;

  65.        return 0;

  66. }

在删除时,如果被删除的节点y为黑色(记删除的节点为x),可能会出现三种情况:

1.    如果y是根,y的红色节点孩子成为了新的根,这样就违反了属性2

2.    如果xp[y]都是红色,这样就违反了属性4.

3.    如果删除y这样就导致y的路径上包含少的黑色节点,这个问题通过记节点x两个黑色节点来进行解决,如果x为红色,则该节点的个数为1,否则记为2.

在进行删除时,主要有下面几种情形:

1.    x的兄弟为红色

2.    x的兄弟节点w为黑色,且w节点的两个孩子都是黑色

3.    x的兄弟节点w为黑色,且w的左孩子是红色,右孩子为黑色

4.    x的兄弟节点w为黑色,且w的右孩子为黑色

当第一种情况时,示意图如下:

对应处理代码如下:

 

  1. //case 1
  2. if(w->color == RED)    
  3. {
  4.     w->color = BLACK;
  5.     parent->color = RED;
  6.     left_rotate(root,parent);
  7.     w = parent->right;
  8. }

第二种情形如下:

相应处理代码如下:

 

  1. if((!w->left || w->left->color == BLACK) && \
  2. (!w->right || w->right->color==BLACK))
  3. {
  4.     w->color = RED;
  5.     x = parent;
  6.     parent = x->parent;
  7. }

第三种情形如下:

对应处理代码如下:

 

  1. if( !w->right || w->right->color == BLACK)
  2. {
  3.     w->color = RED;
  4.     if(w->left)
  5.         w->left->color = BLACK;
  6.     right_rotate(root,w);
  7.     w = parent->right;
  8. }

第四种情形:

对应代码如下:

 

  1. w->color = parent->color;
  2. if(w->right)
  3.     w->right->color = BLACK;
  4. parent->color = BLACK;
  5. left_rotate(root,parent);
  6. x = root->root;
参考资料

算法导论(所有的分析都来自这里)

Linux2.6.24源码

Algorithm(详细介绍了红黑树的由来)

多任务下的数据结构和算法

阅读(14264) | 评论(4) | 转发(0) |
0

上一篇:红黑树的实现

下一篇:回溯法总结

给主人留下些什么吧!~~

appleyuchi2017-04-23 16:50:50

只需将其对应的孩子的父节点指向其父节点的双亲 到底什么意思啊

sting999992014-07-14 18:10:57

你的语言表达真让人费解。不懂。”如果为前两种情形时,只需将其对应的孩子的父节点指向其父节点的双亲“,这表述了个jiba啊

datao09072012-03-30 00:02:48

ChianXu: 如果为前两种情形时,只需将其对应的孩子的父节点指向其父节点的双亲....这句话里面的父节点的双亲?父节点也只有单亲,没有双亲。呵呵.....
有道理,英文为parent,这里只有一个父节点,单亲与双亲意思都一样,谢谢指出!

ChianXu2012-03-14 10:13:28

如果为前两种情形时,只需将其对应的孩子的父节点指向其父节点的双亲....这句话里面的父节点的双亲?父节点也只有单亲,没有双亲。呵呵