algorithm - 红黑树删除算法

Question

从“Introduction to Algorithms 2nd edition”我得到了这个删除算法:

/*
    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(按此顺序放置)构建树(你可以做到 here)，然后删除节点 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;
}

Answer 1

对于没有哨兵的rb-tree版本，删除操作实现如下:

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;
                }