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:

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

Start Free Trial

No credit card required