我正在尝试构建一个红黑树骨架，根据 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 中做错了什么 这扰乱了删除的实现。
谢谢!
最佳答案
我希望我添加了一个答案，以正确的方式进行讨论。
看来我的整个问题不是代码，
但是我比较过的 RBTREE Simulator 链接。
不确定该网站到底发生了什么， 但在几乎放弃并手动检查收到的树之后 从中删除节点 -
似乎每次删除后我都会得到一个完美平衡的红黑树， 已实现所有功能。
很抱歉浪费了您的时间。
晚安
关于c - 删除红黑树中的节点时出现问题(C 代码)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28012126/