Argue that after executing
RB-DELETE-FIXUP, the root of the tree must be black.
First, let's observe that all the cases in
RB-DELETE-FIXUP retains the color
of the root of the subtree. If the deleted node is not the root or an immediate
descendent of the root, the root's color will remain the same, regardless of
The only case that's not obvious is when the deleted node is the root and it has
a single child. In this case,
RB-DELETE-FIXUP will immediately color it red,
and the property will be preserved.