Next: 0.2.4.3 Source Code
Up: 0.2.4 Red-Black Trees
Previous: 0.2.4.1 Insertion Operation
Deletion is about as complicated as insertion. In fact, as you might
expect, deletion is, in essence, a nearly an exact reciprocal operation.
We would always like to delete nodes with red parents and to do so we
are willing to manipulate the tree via rotations and re-coloring operations.
When looking for a node to delete begin at the root of the structure.
If neither of the root's children is red, color the root red. Then,
at each node on the path to the node to be deleted, force the node to