next up previous contents index Search
Next: Source Code Up: 0.2.4 Red-Black Trees Previous: Insertion Operation Deletion

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 become red.

Scott Gasch