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:
- 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 to a leaf contains the same number of black nodes.
The following diagram shows a Red-Black tree:
Take each of the invariants from earlier and check whether the tree satisfies each one of them.
When we look at rebalancing, we will see how the first...
