c - 删除红黑树中的节点时出现问题(C 代码)

Question

我正在尝试构建一个红黑树骨架，根据Cormen 算法。

到目前为止，Insert、Search 和 InsertFixup 以及任何相关方法(如 Left\Right Rotate)都工作正常。

我的问题是删除节点 - 树无法正确修复。

我正在比较删除后的树以下 RB-TREE 模拟器中树的节点: https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

我正在使用的算法:RB-删除

/*
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

删除修复

 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

我的实际代码:

<强>1。移植

static void RBTreeTransplant(RBtree_node_t ** pRoot,
    RBtree_node_t * pDeletedNode, RBtree_node_t * pBrother) {
if (NULL == pDeletedNode->parent) {
    *pRoot = pBrother;
} else if (pDeletedNode == pDeletedNode->parent->left) {
    pDeletedNode->parent->left = pBrother;
} else {
    pDeletedNode->parent->right = pBrother;
}

pBrother->parent = pDeletedNode->parent;
} // RBTreeTransplant

<强>2。删除修复

static void RBDeleteFixUp(RBtree_node_t ** pRoot, RBtree_node_t * pNode) {
RBtree_node_t * pAidNode = NULL;

while ((pNode != *pRoot) && (pNode->color == RB_COLOR_BLACK)) {
    if (pNode == pNode->parent->left) {
        pAidNode = pNode->parent->right; // pAidNode is pNode's brother

        // CASE1: pNode's brother is RED:
        // * Paint pNode's brother(pAidNode) BLACK
        // * Paint pNode's parent RED
        // * Left Rotate pNode's parent
        // * point pAidNode to pNode's Parent right children
        if (pAidNode->color == RB_COLOR_RED) {
            pAidNode->color = RB_COLOR_BLACK;
            pNode->parent->color = RB_COLOR_RED;
            RBRotate(pRoot, pNode->parent, RB_ROTATE_LEFT);
            pAidNode = pNode->parent->right;
            continue;
        } // CASE1

        // CASE2: pNode's brother is BLACK and both his childrens are BLACK
        // * Paint pNode's brother(pAideNode) RED
        // * point pNode to pNode's parent
        if ((pAidNode->left->color == RB_COLOR_BLACK)
                && (pAidNode->right->color == RB_COLOR_BLACK)) {
            pAidNode = RB_COLOR_RED;
            pNode = pNode->parent;
            continue;
        } // CASE2

        //CASE3: pNode's brother and his brother right children is BLACK
        // * Paint pAidNode LEFT children as BLACK
        // * Paint pAidNode as RED
        // * Right Rotate pAidNode
        // * point pAidNode to pNode parent right children
        else if (pAidNode->right->color == RB_COLOR_BLACK) {
            pAidNode->left->color = RB_COLOR_BLACK;
            pAidNode->color = RB_COLOR_RED;
            RBRotate(pRoot, pAidNode, RB_ROTATE_RIGHT);
            pAidNode = pNode->parent->right;
            continue;
        } // CASE3

        //CASE4: pNode's brother is BLACK, and his brother right children is RED
        // * Paint pAidNode as pNode's parent
        // * Paint pNode's parent BLACK
        // * Paint pAidNode right children BLACK
        // * Left Rotate pNode's parent
        // * Set pNode as the new root
        pAidNode->color = pNode->parent->color;
        pNode->parent->color = RB_COLOR_BLACK;
        pAidNode->right->color = RB_COLOR_BLACK;
        RBRotate(pRoot, pNode->parent, RB_ROTATE_LEFT);
        pNode = *pRoot;
    }
} // while

pNode->color = RB_COLOR_BLACK;
 } // RBTreeDeleteFixUp

<强>3。节点删除

static StatusType RBNodeDelete(RBtree_node_t ** pRoot,
    RBtree_node_t * pNode) {
RBtree_node_t * pAidNode = pNode;
RBtree_node_t * pExtraAidNode = NULL;
RBtree_color originalNodeColor = RB_COLOR_BLACK;

if ((NULL == pRoot) || (NULL == *pRoot) || (NULL == pNode)) {
    return INVALID_INPUT;
}

originalNodeColor = pNode->color;

// CASE1: Node to delete has no LEFT.
if (NULL == pNode->left) {
    pExtraAidNode = pNode->right;
    RBTreeTransplant(pRoot, pNode, pNode->right);
} // End of CASE1

// CASE2: Node to delete has LEFT but has no RIGHT
else if (NULL == pNode->right) {
    pExtraAidNode = pNode->left;
    RBTreeTransplant(pRoot, pNode, pNode->left);
} // End of CASE2

// CASE3: Node to delete has both children
else {
    pAidNode = RBTreeMin(pNode->right); // Find Successor
    originalNodeColor = pAidNode->color; // Save color of successor
    pExtraAidNode = pAidNode->right;

    if (pAidNode->parent == pNode) { // Successor has no LEFT cause its nill
        pExtraAidNode->parent = pAidNode;
    } else {
        RBTreeTransplant(pRoot, pAidNode, pAidNode->right);
        pAidNode->right = pNode->right;
        pAidNode->right->parent = pAidNode;
    }

    RBTreeTransplant(pRoot, pNode, pAidNode);
    pAidNode->left = pNode->left;
    pAidNode->left->parent = pAidNode;
    pAidNode->color = pNode->color;
} // End of CASE3

if (originalNodeColor == RB_COLOR_BLACK) {
    RBDeleteFixUp(pRoot, pExtraAidNode);
}

// Free allocated node memory
RBTreeSingleNodeDestroy(pNode);

return SUCCESS;

我很高兴知道我在删除\deletefixup 中做错了什么这扰乱了删除的实现。

谢谢!

Answer 1

我希望我添加了一个答案，以正确的方式进行讨论。

看来我的整个问题不是代码，

但是我比较过的 RBTREE Simulator 链接。

不确定该网站到底发生了什么，但在几乎放弃并手动检查收到的树之后从中删除节点 -

似乎每次删除后我都会得到一个完美平衡的红黑树，已实现所有功能。

很抱歉浪费了您的时间。

晚安