= Red-black tree
{wiki=Red–black_tree}
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 $2\log_2(n+1)$ for $n$ stored keys: a path has at most twice as many real nodes as black nodes, and a <subtree> of <black height> $b$ has at least $2^b-1$ real nodes by <mathematical induction>. The structure therefore supports logarithmic-time directed <binary search tree> lookup.
Back to article page
