0
$\begingroup$

I am working on chapter 13 of CLRS. I am studying how to fix the colors on a red-black tree after deleting a black node.

enter image description here

Suppose we want to delete the node 2. This is a black node. He will be replaced by his rith child in the RB-DELETE algorithm. Because we removed a black node and the node replacing it is black (all NIL are black) then we enter the loop in RB-DELETE-FIXUP. Now this loop immediately asks for x's sibling w to enter different cases. But w in this case would just be 3's right child which is T.nil. It gets even worse from here because we start asking about 3's right child children in case 3 or 4. What's supposed to happen when x does not have siblings?

These are the relevant algorithms:

RB-DELETE-FIXUP(T,x)
1 while x different from T.root and x.color == BLACK
2   if x == x.p.left
3      w = x.p.right
4       if w.color = = RED
5          w.color = BLACK // case 1
6          x.p.color = RED // case 1
7          LEFT-ROTATE(T, x.p)/ // case 1
8           w = x.p.right // case 1
9       if w.left.color == BLACK and w:right:color = = BLACK
10         w.color = RED // case 2
11         x = x.p // case 2
12      else if w.right.color == BLACK
13              w.left.color = BLACK // case 3
14              w.color = RED // case 3
15              RIGHT-ROTATE(T, w)/ // case 3
16              w = x.p.right // case 3
17           w.color = x.p.color // case 4
18           x.p.color = BLACK // case 4
19           w.right.color = BLACK // case 4
20           LEFT-ROTATE(T, x.p) // case 4
21           x = T.root // case 4
22    else (same as then clause with “right” and “left” exchanged)
23 x.color = BLACK
RB-DELETE(T,z) 
1 y = z 
2 y-original-color = y.color
3 if z.left == T.nil
4      x = z.right
5      RB-TRANSPLANT(T, z, z.right)
6 elseif z.right = = T.nil
7        x = z.left
8       RB-TRANSPLANT(T,z,z.left)
9 else y = TREE-MINIMUM(z.right)
10   y-original-color = y.color
11   x = y.right
12   if y.p = = z
13      x.p = y
14   else RB-TRANSPLANT(T,y, y.right)
15           y.right = z.right
16           y.right.p = y
17   RB-TRANSPLANT(T,z,y)
18   y.left = z.left
19   y.left.p = y
20   y.color = z.color
21 if y-original-color == BLACK
22   RB-DELETE-FIXUP(T,x)

```
$\endgroup$
1
  • $\begingroup$ Not everybody know by heart all the algorithms in the CLRS. You should remind us of the algorithm you are trying to work on. $\endgroup$
    – Nathaniel
    Mar 29, 2021 at 14:51

1 Answer 1

2
$\begingroup$

Let $x$ denote the node you want to delete and $p(x)$ its parent. If $x$ has no sibling, then it necessarily means that $x$ is a red node, otherwise two path from $p(x)$ could have a different number of black nodes (therefore the tree is not a Red-black tree).

So the situation where $x$ is black and has no sibling can never happen (and the tree in your example is not a Red-black tree).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.