Exercise 13.4.1

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

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.