RED-BLACK TREE the balanced tree in your standard library
The balanced search tree that actually runs your code: C++ std::map, Java TreeMap, the Linux scheduler. It colours each node red or black and keeps two rules — no two reds in a row, and every root-to-leaf path has the same number of blacks — which alone forces the tree to stay within 2 log n of perfect. Looser than AVL, cheaper to update.
THE TECHNIQUE two colours, two rules, cheap repair
Colour the root black; new nodes red. Two invariants: no red node has a red child, and every path from a node to its leaves has the same black-count. An insert that breaks them is fixed by recolouring and at most a couple of rotations — far fewer than AVL needs. Insert values and see the colours and heights. live demo
HISTORY & CREDIT a B-tree wearing two colours
“Guibas & Sedgewick invented it in 1978” — they invented re-dressed a structure Rudolf Bayer had in 1972. cited
1972 · Rudolf Bayer describes symmetric binary B-trees — a binary encoding of the 2-3-4 tree. The structure already exists. 1978 · Leonidas Guibas & Robert Sedgewick give it the red/black colouring and a uniform rebalancing framework (“A Dichromatic Framework”) — the abstraction that made it teachable and popular. the colour is on the edge · originally the colour marked the link to a node, standing for “this child is part of the same B-tree node”; the familiar “the node is red” is the later CLRS reformulation (equivalent). in the wild · std::map, TreeMap, the Linux CFS scheduler and timers — the default ordered map almost everywhere.
A red-black tree is a 2-3-4 tree in disguise; the colours just encode which nodes were fused. Bayer, 1972
RECOMMEND FOR I-13 the same pointer wall, one bit richer
Like the AVL tree (072), a red-black tree is dynamically linked nodes — plus a single colour bit per node:
// node: {key, left, right, colour(1 bit)} ; inserts recolour + rotate
// the colour bit is trivial; the LINKED structure is the wall
Recommend: the same aggregate/pointer wall as AVL (072) and the trie (074) — heap-allocated nodes with references the rebalancing relinks. The colour is one bit (the integrated bitwise handles it trivially); the rules (compare black-heights, check red-red) are scalar and run; only the node graph is the want. The pointerless node-arena encoding (key[], left[], right[], colour[] as parallel arrays into a pool) runs on I-13’s arrays — the honest way the corpus would express any dynamic tree today. Note: three darts now land on the same frontier — AVL, red-black, and the trie all want heap-allocated linked nodes; the array-of-references / node-arena is their shared shape.