那些遇到过的问题

红黑树删除算法

sma*_*llB 4 algorithm red-black-tree

从"算法简介第2版"我得到了这个删除算法: 

/*
    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
    */
Run Code Online (Sandbox Code Playgroud)

现在这个算法几乎没有问题,一个主要问题是如果你尝试用节点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
Run Code Online (Sandbox Code Playgroud)

实施

    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;
}
Run Code Online (Sandbox Code Playgroud)

小智 9

对于没有标记的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;
}
Run Code Online (Sandbox Code Playgroud)

它使用Java,但可以轻松移植到任何语言.

以下代码与您的实现有所不同:

在这里筑巢:

            } else {
                if (isBlack(w._right)) {
Run Code Online (Sandbox Code Playgroud)

和这里:

            } else {
                if (isBlack(w._left)) {
Run Code Online (Sandbox Code Playgroud)

这里没有哨兵的东西:

    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;
    }
Run Code Online (Sandbox Code Playgroud)

然后在这里:

        deleteFixUp(tree, x, xParent, yIsLeft);
Run Code Online (Sandbox Code Playgroud)

在deleteFixUp()-只是看的使用nodeParent和nodeIsLeft在这个地方,最后:

                if (w._right != null) {
                    w._right._isRed = false;
                }
Run Code Online (Sandbox Code Playgroud)

还有这个:

                if (w._left != null) {
                    w._left._isRed = false;
                }
Run Code Online (Sandbox Code Playgroud)

ant*_*kos 1

节点的颜色Nil定义为黑色。该代码包含诸如以下的语句

\n\n
if (y->color_ == Red)\n
Run Code Online (Sandbox Code Playgroud)\n\n

y如果是一个就会崩溃nullptr。如果您将所有此类比较替换为调用安全is_red()和is_black()检查Nil节点的函数，那么一些崩溃就会消失。

\n\n

在这里筑巢

\n\n
        else if(z == z->parent_->right_)\n        {\n            z = z->parent_;\n            left_rotate(t,z);\n        }\n        z->parent_->color_ = Black;\n        z->parent_->parent_->color_ = Red;\n        right_rotate(t,z->parent_->parent_);\n
Run Code Online (Sandbox Code Playgroud)\n\n

与此处的嵌套不匹配：

\n\n
 9                   else if z = right[p[z]]\n10                           then z \xe2\x86\x90 p[z]         \n11                                LEFT-ROTATE(T, z)\n12                           color[p[z]] \xe2\x86\x90 BLACK   \n13                           color[p[p[z]]] \xe2\x86\x90 RED  \n14                           RIGHT-ROTATE(T, p[p[z]])  \n
Run Code Online (Sandbox Code Playgroud)\n\n

其他事情可能也需要调试，但我不认为 CLR 是罪魁祸首。

\n

归档时间：

查看次数：

13946 次

最近记录：

12 年，6 月 前
相关归档
如何找到算法的时间复杂度 845
C中用于比特反转的最有效算法(从MSB-> LSB到LSB-> MSB) 232
"模糊匹配"字符串的算法 24
确定两条光线是否相交 20
如何在C++中创建几个没有硬编码循环的向量组合？ 14
图:找到小于O(| V |)的接收器 - 或者显示无法完成 10
我应该使用BFS,DFS进行树遍历还是有序,后期订购,预订？ 10
更改矩形大小时重新计算光线跟踪/投射成本 10
Python中的空填字游戏解算器 7
如何在没有压缩的情况下解码PNG文件的IDAT块 6
难疑归档
'git pull'和'git fetch'有什么区别？ 11447
如何将空目录添加到Git存储库？ 4039
如何将多行中的文本连接成SQL Server中的单个文本字符串？ 1813
在不应用它的情况下查看存储中的内容 1650
如何使用逗号作为千位分隔符在JavaScript中打印数字 1589
如何离开/退出/停用python virtualenv？ 1461
如何将堆栈跟踪转换为字符串？ 1435
如何垂直对齐div内的图像？ 1371
在JavaScript中修剪字符串？ 1285
如何使用Windows开发机器为iPhone开发？ 1161