A red-black tree colours each stored node red or black, treats absent-child sentinels as black, permits no red node to have a red child, and gives every path from a node to an absent-child sentinel the same number of black nodes. We also require a black root. These invariants bound its height of a binary tree by for stored keys: a path has at most twice as many real nodes as black nodes, and a subtree of black height has at least real nodes by mathematical induction. The structure therefore supports logarithmic-time directed binary search tree lookup.
In the usual bottom-up algorithm, insert a red node by the binary search tree rule. If its parent is black, no repair is needed. If its parent and uncle are red, recolour both black and recolour the grandparent red, then continue upward. If the uncle is black, an inner configuration first rotates the parent to become an outer configuration; rotating the grandparent and exchanging its colour with the parent's resolves the red-red conflict. Apply the left/right mirror cases as needed and finish with a black root. The tree rotations preserve key order, and the colour changes preserve equal black height. Different valid insertion conventions can produce different valid red-black trees, so a worked trace must identify its convention.
A red-black tree with no red stored nodes is a perfect binary tree. Indeed, every root-to-sentinel path has equal length because every real node is black; a missing branch at an earlier level would make its path shorter. Thus every real level is full. Its size is for some number of real levels. Conversely, colouring every stored node of a perfect binary tree black satisfies every red-black invariant. This proves both directions of the size criterion.
For a node of a red-black tree, count black nodes strictly below on any path to an absent-child sentinel, including that black sentinel. The red-black invariants make this count independent of the path. Other conventions omit the sentinel or count ; specify the convention when using numerical values. Equality of the counts, rather than their common additive offset, is what the balancing condition requires.
