红黑树分析(删除部分)

红黑树的删除

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

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

1.             只有左孩子存在

2.             只有右孩子存在

3.             两孩子均存在

4.             两孩子均不存在

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

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

 

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

{

struct rb_node *child,*parent;

       int color;

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

       if(!node->left)

              child = node->right;

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

       else if(!node->right)

              child = node->left;

       //否则寻找后继节点

       else

       {

              struct rb_node *old = node,*left;

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

              node = node->right;

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

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

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

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

              color = node->color;

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

              if(child) child->parent = parent;

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

                     parent->right = child;

                     parent = node;

              } else

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

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

              node->parent = old->parent;

              node->color = old->color;

              node->right = old->right;

              node->left = old->left;

              //修改双亲节点

              if(old->parent)

              {

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

                            old->parent->left = node;

                     else old->parent->right = node;

              } else

                     root->root = node;

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

              old->left->parent = node;

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

              if(old->right)

                     old->right->parent = node;

              goto color;

       }

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

       parent = node->parent;

       color = node->color;



       if(child)

              child->parent = parent;

       if(parent)

       {

              if(parent->left == node)

                     parent->left = child;

              else parent->right = child;

       } else

              root->root = child;

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

       if(color == BLACK)

              __rb_tree_erase_fixup(root,parent,child);

       root->len --;

       return 0;

}

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

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

2.    如果x和p[y]都是红色，这样就违反了属性4.

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

在进行删除时，主要有下面几种情形：

1.    x的兄弟为红色

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

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

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

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

对应处理代码如下:

 

//case 1
if(w->color == RED)
{
    w->color = BLACK;
    parent->color = RED;
    left_rotate(root,parent);
    w = parent->right;
}

第二种情形如下:

相应处理代码如下:

 

if((!w->left || w->left->color == BLACK) && \
(!w->right || w->right->color==BLACK))
{
    w->color = RED;
    x = parent;
    parent = x->parent;
}

第三种情形如下:

对应处理代码如下:

 

if( !w->right || w->right->color == BLACK)
{
    w->color = RED;
    if(w->left)
        w->left->color = BLACK;
    right_rotate(root,w);
    w = parent->right;
}

第四种情形:

对应代码如下:

 

w->color = parent->color;
if(w->right)
    w->right->color = BLACK;
parent->color = BLACK;
left_rotate(root,parent);
x = root->root;

参考资料

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

Linux2.6.24源码

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

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