Explain why if in RBDELETE both x and px are red then proper

Explain why, if in RB-DELETE both x and p[x] are red, then property 4 (If a node is red, both of its children are black) is restored by the call RB-DELETE-FIXUP(T, x).

Solution

After meshing out a node the procedure RB-DELETE calls a backup procedure RB-DELETEFIXUP that changes colors and performs rotations to restore the red-black properties. A call to RB-DELETE-FIXUP is made in lines 16 – 17 if y is black. If y is red, the red-black properties still hold when y is spliced out.

The node x is passed to RB-DELETE-FIXUP is one of two nodes that is either the node that was y’s single child before y was meshed out if y had a child that was not the sentinel NULL, or it y had no children, x is the sentinel NULL. In the latter case, the unconditional assignment in line 7 guarantees that x’s parent is now the node that was previously y’s parent, whether x is a key-bearing internal node or the sentinel NULL.

x’s sibling is red : It occurs when node w, the sibling of node x, is red. Since w must have black children, we can switch the colors of w and x->p and then perform a leftrotation on x->p without violating any of the red-black properties. The new sibling of x, which is one of w\'s children prior to the rotation, is now black, and thus we have converted case 1 into case 2, 3, or 4.