# Cormen RB-DELETE_FIXUP(T,x) when x has no siblings

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.

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)

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

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).