logo标签列表

红黑树删除算法

algorithmred-black-tree
5
从《算法导论第二版》中，我得到了这个删除算法：

/*
    RB-DELETE(T, z)
    1 if left[z] = nil[T] or right[z] = nil[T]
    2    then y ← z
    3    else y ← TREE-SUCCESSOR(z)
    4 if left[y] ≠ nil[T]
    5    then x ← left[y]
    6    else x ← right[y]
    7 p[x] ← p[y]
    8 if p[y] = nil[T]
    9    then root[T] ← x
    10    else if y = left[p[y]]
    11            then left[p[y]] ← x
    12            else right[p[y]] ← x
    13 if y != z
    14    then key[z] ← key[y]
    15         copy y's satellite data into z
    16 if color[y] = BLACK
    17    then RB-DELETE-FIXUP(T, x)
    18 return y
    */

现在该算法存在一些问题，其中一个主要问题是如果您尝试使用节点1、2、3、4、5、6（按此顺序放置）构建树（您可以在此处进行），然后删除节点2，则该算法的第4、5和6行将返回nullptr（x == nullptr）。有谁能帮我解决这个问题吗？
以下是辅助算法（来自同一本书）：
TREE-SUCCESSOR(x)
1  if right[x] ≠ NIL
2      then return TREE-MINIMUM (right[x])
3  y ← p[x]
4  while y ≠ NIL and x = right[y]
5      do x ← y
6         y ← p[y]
7  return y

 TREE-MINIMUM (x)
1  while left[x] ≠ NIL
2      do x ← left[x]
3  return x

 RB-DELETE-FIXUP(T, x)
 1 while x ≠ root[T] and color[x] = BLACK
 2     do if x = left[p[x]]
 3           then w ← right[p[x]]
 4                if color[w] = RED
 5                   then color[w] ← BLACK                        ▹  Case 1
 6                        color[p[x]] ← RED                       ▹  Case 1
 7                        LEFT-ROTATE(T, p[x])                    ▹  Case 1
 8                        w ← right[p[x]]                         ▹  Case 1
 9                if color[left[w]] = BLACK and color[right[w]] = BLACK
10                   then color[w] ← RED                          ▹  Case 2
11                        x p[x]                                  ▹  Case 2
12                   else if color[right[w]] = BLACK
13                           then color[left[w]] ← BLACK          ▹  Case 3
14                                color[w] ← RED                  ▹  Case 3
15                                RIGHT-ROTATE(T, w)              ▹  Case 3
16                                w ← right[p[x]]                 ▹  Case 3
17                         color[w] ← color[p[x]]                 ▹  Case 4
18                         color[p[x]] ← BLACK                    ▹  Case 4
19                         color[right[w]] ← BLACK                ▹  Case 4
20                         LEFT-ROTATE(T, p[x])                   ▹  Case 4
21                         x ← root[T]                            ▹  Case 4
22        else (same as then clause with "right" and "left" exchanged)
23 color[x] ← BLACK

LEFT-ROTATE(T, x)
 1  y ← right[x]            ▹ Set y.
 2  right[x] ← left[y]      ▹ Turn y's left subtree into x's right subtree.
 3  p[left[y]] ← x
 4  p[y] ← p[x]             ▹ Link x's parent to y.
 5  if p[x] = nil[T]
 6     then root[T] ← y
 7     else if x = left[p[x]]
 8             then left[p[x]] ← y
 9             else right[p[x]] ← y
10  left[y] ← x             ▹ Put x on y's left.
11  p[x] ← y


RB-INSERT(T, z)
 1  y ← nil[T]
 2  x ← root[T]
 3  while x ≠ nil[T]
 4      do y ← x
 5         if key[z] < key[x]
 6            then x ← left[x]
 7            else x ← right[x]
 8  p[z] ← y
 9  if y = nil[T]
10     then root[T] ← z
11     else if key[z] < key[y]
12             then left[y] ← z
13             else right[y] ← z
14  left[z] ← nil[T]
15  right[z] ← nil[T]
16  color[z] ← RED
17  RB-INSERT-FIXUP(T, z)

RB-INSERT-FIXUP(T, z)
 1 while color[p[z]] = RED
 2     do if p[z] = left[p[p[z]]]
 3           then y ← right[p[p[z]]]
 4                if color[y] = RED
 5                   then color[p[z]] ← BLACK                    ▹ Case 1
 6                        color[y] ← BLACK                       ▹ Case 1
 7                        color[p[p[z]]] ← RED                   ▹ Case 1
 8                        z ← p[p[z]]                            ▹ Case 1
 9                   else if z = right[p[z]]
10                           then z ← p[z]                       ▹ Case 2
11                                LEFT-ROTATE(T, z)              ▹ Case 2
12                           color[p[z]] ← BLACK                 ▹ Case 3
13                           color[p[p[z]]] ← RED                ▹ Case 3
14                           RIGHT-ROTATE(T, p[p[z]])            ▹ Case 3
15           else (same as then clause
                         with "right" and "left" exchanged)
16 color[root[T]] ← BLACK

实现

    enum Color {Black,Red};

    template<class Key>
    struct Node
    {
        Key* key_;
        Color color_;
        Node* parent_;
        Node* left_;
        Node* right_;
        Node(Key k,Node* parent = nullptr, Node* left = nullptr,Node* right = nullptr):key_(new Key[2]),
            color_(Red),
            parent_(parent),
            left_(left),
            right_(right)
        {
            key_[0] = k;
            key_[1] = '\0';
        }
    };

template<class Key>
class Tree
{
    Node<Key>* head_;
    typedef Key* key_pointer;
    typedef Node<Key>* pointer;
    typedef Node<Key> value_type;
public:
    Tree(Key k):head_(new value_type(k))
    {
        head_->color_ = Black;
    }

    ~Tree()
    {
        delete head_;
    }

    pointer root()const
    {
        auto root = head_;
        while (root->parent_)
        {
            root = root->parent_;
        }
        return root;
    }

    void root(pointer root)
    {
        head_ = root;
    }

    pointer parent()const
    {
        return head_->parent_;
    }

    void parent(pointer parent)
    {
        head_->parent_ = parent;
    }

    pointer left()const
    {
        return head_->left_;
    }

    void left(pointer left)
    {
        head_->left_ = left;
    }

    pointer right()const
    {
        return head_->right_;
    }

    void right(pointer right)
    {
        head_->right_ = right;
    }

    key_pointer key()const
    {
        return head_->key_;
    }
};

template<class Tree,class Node>
void left_rotate(Tree* t, Node* x)
{
    auto y = x->right_;
    x->right_ = y->left_;
    if (y->left_)
    {
        y->left_->parent_ = x;
    }
    y->parent_ = x->parent_;
    if (!x->parent_)
    {
        t->root(y);
    }
    else if(x == x->parent_->left_)
    {
        x->parent_->left_ = y;
    }
    else
    {
        x->parent_->right_ = y;
    }
    y->left_ = x;
    x->parent_ = y;
}

template<class Tree,class Node>
void right_rotate(Tree* t, Node* x)
{
    auto y = x->left_;
    x->left_ = y->right_;
    if (y->right_)
    {
        y->right_->parent_ = x;
    }
    y->parent_ = x->parent_;
    if (!x->parent_)
    {
        t->root(y);
    }
    else if(x == x->parent_->right_)
    {
        x->parent_->right_ = y;
    }
    else
    {
        x->parent_->left_ = y;
    }
    y->right_ = x;
    x->parent_ = y;
}


template<class Tree, class Node_Value>
void insert(Tree* t, Node_Value n)
{
    auto z = make_node(n);
    auto x = t->root();
    decltype(z) y = nullptr;
    while(x)
    {
        y = x;
        if (*z->key_ < *x->key_)
        {
            x = x->left_;
        }
        else
        {
            x = x->right_;
        }
    }
    z->parent_ = y;
    if (!y)
    {
        t->root(z);
    }
    else
    {
        if (*z->key_ < *y->key_)
        {
            y->left_ = z;
        }
        else
        {
            y->right_ = z;
        }
    }
    z->left_ = nullptr;
    z->right_ = nullptr;
    z->color_ = Red;
    insert_fix_up(t,z);
}
template<class Tree, class Node>
void insert_fix_up(Tree* t, Node* z)
{
    while (z->parent_->color_ == Red)
    {
        if (z->parent_ == z->parent_->parent_->left_)
        {
            auto y = z->parent_->parent_->right_;

            if (y->color_ == Red)
            {
                z->parent_->color_ = Black;
                y->color_ = Black;
                z->parent_->parent_->color_ = Red;
                z = z->parent_->parent_;
            }
            else if(z == z->parent_->right_)
            {
                z = z->parent_;
                left_rotate(t,z);
            }
            z->parent_->color_ = Black;
            z->parent_->parent_->color_ = Red;
            right_rotate(t,z->parent_->parent_);
        }
        else
        {
            auto y = z->parent_->parent_->left_;

            if (y->color_ == Red)
            {
                z->parent_->color_ = Black;
                y->color_ = Black;
                z->parent_->parent_->color_ = Red;
                z = z->parent_->parent_;
            }
            else if(z == z->parent_->left_)
            {
                z = z->parent_;
                right_rotate(t,z);
            }
            z->parent_->color_ = Black;
            z->parent_->parent_->color_ = Red;
            left_rotate(t,z->parent_->parent_);
        }
    }
    t->root()->color_ = Black;
}

template<class Node>
Node* tree_minimum(Node* x)
{
    while (x->left_)
    {
        x = x->left_;
    }
    return x;
}

template<class Node>
Node* tree_successor(Node* x)
{
    if (x->right_)
    {
        return tree_minimum(x->right_);
    }
    auto y = x->parent_;
    while (y && x == y->right_)
    {
        x = y;
        y = y->parent_;
    }
    return y;
}

template<class Tree, class Node>
Node* rb_delete(Tree* t,Node* z)
{
    Node* x = nullptr;
    Node* y = nullptr;
    if (!z->left_ || !z->right_)
    {
        y = z;
    }
    else
    {
        y = tree_successor(z);
    }
    if (y->left_)
    {
        x = y->left_;
    }
    else
    {
        x = y->right_;
    }
    x->parent_ = y->parent_;
    if (!y->parent_)
    {
        t->root(x);
    }
    else if (y == y->parent_->left_)
    {
        y->parent_->left_ = x;
    }
    else
    {
        y->parent_->right_ = x;
    }
    if (y != z)
    {
        z->key_ = y->key_; 
    }
    if (y->color_ = Black)
    {
        rb_delete_fix_up(t,x);
    }
    return y;
}

template<class Tree, class Node>
void rb_delete_fix_up(Tree*& t,Node*& x)
{
    while (x != t->root() && x->color_ == Black)
    {
        Node* w = nullptr;
        if (x == x->parent_->left_)
        {
            w = x->parent_->right_;
            if (w->color_ == Red)
            {
                w->color_ = Black;
                x->parent_->color_ = Red;
                left_rotate(t,x->parent_);
                w = x->parent_->right_;
            }
            if (w->left_->color_ == Black && w->right_->color_ == Black)
            {
                w->color_ = Red;
                x = x->parent_;
            }
            else if(w->right_->color_ == Black)
            {
                w->left_->color_ = Black;
                w->color_ = Red;
                right_rotate(t,w);
                w = x->parent_->right_;
            }
            w->color_ = x->parent_->color_;
            x->parent_->color_ = Black;
            w->right_->color_ = Black;
            left_rotate(t,x->parent_);
            x = t->root();
        }
        else
        {
                w = x->parent_->left_;
            if (w->color_ == Red)
            {
                w->color_ = Black;
                x->parent_->color_ = Red;
                right_rotate(t,x->parent_);
                w = x->parent_->left_;
            }
            if (w->right_->color_ == Black && w->left_->color_ == Black)
            {
                w->color_ = Red;
                x = x->parent_;
            }
            else if(w->left_->color_ == Black)
            {
                w->right_->color_ = Black;
                w->color_ = Red;
                left_rotate(t,w);
                w = x->parent_->left_;
            }
            w->color_ = x->parent_->color_;
            x->parent_->color_ = Black;
            w->left_->color_ = Black;
            right_rotate(t,x->parent_);
            x = t->root();
        }

    }
    x->color_ = Black;
}
template<class Key>
Node<Key>* make_node(Key k)
{
    return new Node<Key>(k);
}

int _tmain(int argc, _TCHAR* argv[])
{
    auto t = new Tree<int>(1);
    insert(t,2);
    insert(t,3);
    insert(t,4);
    insert(t,5);
    insert(t,6);
    rb_delete(t,t->left());
    return 0;
}
1
你是否检查过你的问题是否在这里列出：http://www.cs.dartmouth.edu/~thc/clrs-2e-bugs/bugs.php？ - Philipp
你能让我们看看你的实际实现吗？ - Patrick
@Patric和Nico，没问题，请给我5分钟，我将向您展示所有这些算法的实现。就我所知，无论是插入还是删除都不能正常工作（对于以此顺序构建的树：1,2,3,4,5,6）。 - smallB
@Patric，我刚刚上传了我的实现。 - smallB
@Patric，我不完全确定我发布的链接使用了这个确切的算法。 - smallB
显示剩余13条评论
2个回答
9

如果不使用哨兵的红黑树版本，则删除操作的实现如下：

SWRedBlackNode delete(SWRedBlackTree tree, SWRedBlackNode node) {
    SWRedBlackNode y;
    if (node._left == null || node._right == null) {
        y = node;
    } else {
        y = node.getSuccessor();
    }

    SWRedBlackNode x;
    if (y._left != null) {
        x = y._left;
    } else {
        x = y._right;
    }
    if (x != null) {
        x._parent = y._parent;
    }
    SWRedBlackNode xParent = y._parent;

    boolean yIsLeft = false;
    if (y._parent == null) {
        tree._root = x;
    } else if (y == y._parent._left) {
        y._parent._left = x;
        yIsLeft = true;
    } else {
        y._parent._right = x;
        yIsLeft = false;
    }

    if (y != node) {
        node._value = y._value;
    }

    if (!y._isRed) {
        deleteFixUp(tree, x, xParent, yIsLeft);
    }

    return y;
}

private void deleteFixUp(SWRedBlackTree tree, SWRedBlackNode node, SWRedBlackNode nodeParent, boolean nodeIsLeft) {
    while (node != tree._root && isBlack(node)) {
        SWRedBlackNode w;
        if (nodeIsLeft) {
            w = nodeParent._right;
            if (isRed(w)) {
                w._isRed = false;
                nodeParent._isRed = true;
                leftRotate(tree, nodeParent);
                w = nodeParent._right;
            }

            if (isBlack(w._left) && isBlack(w._right)) {
                w._isRed = true;
                node = nodeParent;
                nodeParent = node._parent;
                nodeIsLeft = (node == nodeParent._left);
            } else {
                if (isBlack(w._right)) {
                    w._left._isRed = false;
                    w._isRed = true;
                    rightRotate(tree, w);
                    w = nodeParent._right;
                }

                w._isRed = nodeParent._isRed;
                nodeParent._isRed = false;
                if (w._right != null) {
                    w._right._isRed = false;
                }
                leftRotate(tree, nodeParent);
                node = tree._root;
                nodeParent = null;
            }
        } else { /* nodeIsLeft == false */
            w = nodeParent._left;
            if (isRed(w)) {
                w._isRed = false;
                nodeParent._isRed = true;
                rightRotate(tree, nodeParent);
                w = nodeParent._left;
            }

            if (isBlack(w._right) && isBlack(w._left)) {
                w._isRed = true;
                node = nodeParent;
                nodeParent = node._parent;
                nodeIsLeft = (node == nodeParent._left);
            } else {
                if (isBlack(w._left)) {
                    w._right._isRed = false;
                    w._isRed = true;
                    leftRotate(tree, w);
                    w = nodeParent._left;
                }

                w._isRed = nodeParent._isRed;
                nodeParent._isRed = false;
                if (w._left != null) {
                    w._left._isRed = false;
                }
                rightRotate(tree, nodeParent);
                node = tree._root;
                nodeParent = null;
            }
        }
    }

    node._isRed = false;
}

这段代码是用Java编写的，但很容易移植到其他语言。

以下代码与您的实现不同：

这里嵌套了：

            } else {
                if (isBlack(w._right)) {

并且在这里：

            } else {
                if (isBlack(w._left)) {

这里是没有哨兵的内容：

    if (x != null) {
        x._parent = y._parent;
    }
    SWRedBlackNode xParent = y._parent;

    boolean yIsLeft = false;
    if (y._parent == null) {
        tree._root = x;
    } else if (y == y._parent._left) {
        y._parent._left = x;
        yIsLeft = true;
    } else {
        y._parent._right = x;
        yIsLeft = false;
    }

接下来是：

        deleteFixUp(tree, x, xParent, yIsLeft);

在deleteFixUp()中 - 只需查找nodeParent和nodeIsLeft的使用情况，并最终在此处进行：

                if (w._right != null) {
                    w._right._isRed = false;
                }

并且这个：

                if (w._left != null) {
                    w._left._isRed = false;
                }
应该是(nodeParent != null && node == nodeParent._left)，而不是(node == nodeParent._left)。否则当你到达根节点时，会得到空指针异常。除此之外，这是一个非常优秀的删除/删除修复解决方案，没有哨兵。 - Etai
这里缺少了一个空值测试（可以将deleteFixUp的最后一行更改为if (node！= null) node._isRed = false; 或者将if（！y._isRed）{deleteFixUp（tree，x，xParent，yIsLeft）;} 更改为if（！y._isRed && tree._root！= null）{deleteFixUp（tree，x，xParent，yIsLeft）;}），因为当树是单个黑节点并且您删除它时，会出现NullPointerException。 - Peter Taylor
@trog 我在哪里能找到这段代码的其余部分？也就是左旋转、右旋转、获取后继节点等等。 - m-a-r-c-e-l-i-n-o
1

Nil节点的颜色被定义为黑色。代码包含如下语句：

if (y->color_ == Red)

如果y是nullptr，那么程序将崩溃。如果您将所有这样的比较替换为调用安全的is_red()和is_black()函数来检查Nil节点，则一些崩溃将消失。

这里的嵌套

        else if(z == z->parent_->right_)
        {
            z = z->parent_;
            left_rotate(t,z);
        }
        z->parent_->color_ = Black;
        z->parent_->parent_->color_ = Red;
        right_rotate(t,z->parent_->parent_);

这里的嵌套不匹配：

 9                   else if z = right[p[z]]
10                           then z ← p[z]         
11                                LEFT-ROTATE(T, z)
12                           color[p[z]] ← BLACK   
13                           color[p[p[z]]] ← RED  
14                           RIGHT-ROTATE(T, p[p[z]])

其他的东西可能也需要调试，但我不认为CLR会有责任。

谢谢你的回答，关于嵌套，还有其他应该怎么做吗？在else if里面吗？ - smallB
关于 is_red() || is_black() 是什么意思？如果它是 nullptr，我该怎么办？跳过只提到 null 变量的那一行吗？还是跳过整个代码块？这就是让我生气的地方，这本书的第三版，但你仍然不能根据他们的算法构建树。可悲。 - smallB
删除整个过程？这太糟糕了。试着按顺序构建树1、2、3、4、5、6，然后删除节点1。 - smallB
@smallB is_red() 应该在 nullptr 上返回 false，而 is_black() 应该返回 true。嵌套应该像 else { if (...) { ... } ... } 这样。 - antonakos
感谢您对“嵌套”的评论。现在它能正常工作了。但是“删除”出了问题。试一试，您就会发现。 - smallB
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接