 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.