I'm trying to build a Red-Black Tree skeleton, according to cormen algorithms.
So far Insert, Search and InsertFixup and any related methods (like Left\Right Rotate) are all working properly.
My problem is with deleting a node - The tree doesn't fix properly.
I'm comparing my tree after deleting a node to the tree in the following RB-TREE-simulator: https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
The algorithms i'm using: RB-DELETE
/*
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
DELETE-FIXUP
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
And My actual code:
1. Transplant
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. DeletFixUp
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. NodeDelete
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;
I'll be glad to know what am i doing wrong in my delete\deletefixup that messing the delete implementation.
Thanks!
I hope i'm adding an answer to thread the correct way.
Seems like my whole problem was not the code,
but the RBTREE Simulator link i've compared with.
Not sure what's really going on in that site, but after almost giving up and manually checking the received tree after deleting of nodes from it -
it seems that after each delete i get a perfectly balanced Red Black Tree, with all of features implemented.
Sorry for wasting any of your time.
Good Night