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:
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: