Learning Functional Data Structures and Algorithms

Red-Black trees

Given this rotation algorithm, we can now look at the core Red-Black tree.

A Red-Black tree node always has a color, either red or black, with the following invariants:

• A red node can never have a red child
• Every path from the root to an empty node contains the same number of black nodes

An empty node is a leaf nil node. This nil node indicates termination and is also known as a sentinel node.

Here is an example of a Red-Black tree. Note that each node is annotated with its black height. The black height is the number of black nodes from the node to the leaf.

Note these important points:

1. The root is always black.
2. Every leaf is black.
3. Both the children of a red node are black (as a red node cannot have a red child).
4. Every path from a node ...