Red-Black Tree Algorithm

The red-black tree algorithm is the set of recoloring and rotation operations that keep a red-black tree, a self-balancing binary search tree, within its balance guarantee after an insertion or deletion, by restoring five structural properties: every node is colored either red or black, every null child is treated as black, a red node never has a red child, every path from a given node to any leaf beneath it passes through the same number of black nodes, and the root is always black. Rebalancing after a change relies on a mix of recoloring nodes and at most a small, bounded number of rotations rather than a full rebalancing pass, so it restores the tree's properties in time that is on average constant and never worse than proportional to the logarithm of the tree's size, guaranteeing that the longest path from root to leaf never exceeds twice the length of the shortest such path. Leonidas Guibas and Robert Sedgewick derived the modern red-black tree in their 1978 paper "A Dichromatic Framework for Balanced Trees," building on Rudolf Bayer's 1972 symmetric binary B-tree, and by their own account chose the color red for largely practical reasons, since it printed most clearly on the laser printer available to them at Xerox PARC.