Red Black Tree Removal Algorithm

This page details the node removal algorithm for red black trees in the case of both the removed node and its successor being black (null nodes are considered black).

After removing a black node with a black successor from a red black tree the node made null is considered a double black node. There are three cases to restore the RBT (red black tree) properties in this situation. The algorithms for the cases must be done until there is no double black node.

The Three Cases

• The double black node has a black sibling with at least one red child (RBT properties are completely restored by this case's algorithm)

• The double black node has a black sibling with no red children (May still have an RBT property violation after this case's algorithm)

• The double black node has a red sibling (Will still have an RBT property violation after this case's algorithm)

MORE INFO