C++ Footprint and Performance Optimization

Red/Black Trees

Red/Black trees, introduced by R. Bayer, are binary search trees that adhere to a few extra structuring rules, and that have a few extra properties in each node. These new rules and properties make it easier to keep the tree structure balanced when inserting and deleting elements. The extra properties found in the nodes of a Red/Black tree are

1. A pointer to the parent of the node.

2. A code indicating the color of the node.

In a Red/Black tree, the color code of each node is either red or black. The extra structuring rules that Red/Black trees adhere to are

1. If a node is red, its children have to be black.

2. Each leaf is a NIL node and is black.

3. The path in the tree from the root to any leaf contains the same number of black nodes.

A NIL ...