II · Trees, with shape

Red-black tree

Almost balanced, much faster to maintain.

1972 · 1978 · Rudolf Bayer; reformulated by Guibas & Sedgewick

The story

Bayer's "symmetric binary B-tree" of 1972 is the same idea. But Guibas and Sedgewick's 1978 reformulation, with red and black node colours, made the invariant memorable. The colour rules let the tree be 2× as deep as a perfectly balanced one in the worst case, but every operation is O(log n) and rebalancing is cheaper than AVL.

How it works

Every node is red or black. Five rules: root black; every leaf (NIL) black; red nodes have black children; every root-to-leaf path has the same number of black nodes; new nodes are red. Inserts and deletes recolour and rotate locally to restore the invariants.

Where it lives

Linux kernel's CFS process scheduler, virtual memory areas, epoll. C++ std::map, std::set. Java's TreeMap, TreeSet. The most-deployed balanced tree.

The key insight

When you read kernel source code and find a "rb_tree", you are reading code that runs on every Linux machine in the world. It's probably the most-executed data structure that isn't a hash table.

More in Trees, with shape

Binary search tree Sorted, but with shortcuts. AVL tree Always height-balanced, to within one. B-tree / B+ tree The shape of a database index. Heap (binary heap) A priority queue you can grep. Skip list Probabilistic balance, beautifully. Trie (prefix tree) A tree you walk one character at a time. Segment tree Range queries in logarithmic time. Fenwick tree (BIT) Prefix sums, with constant tweaks. Treap BST and heap, secretly the same tree. Splay tree No metadata — and surprising amortised guarantees.

Across the cabinet

III Robin Hood hashing Steal from the rich, give to the poor. III Consistent hashing Hashing that survives node changes. III Perfect hashing Zero collisions, by design. IV Bloom filter A set, in a thousandth of the space. IV HyperLogLog Count distinct, in 12 KB. IV Count-Min sketch Approximate frequencies, in tiny memory. IV MinHash Set similarity, in a few hashes. IV t-digest Quantiles, fairly accurate, fully streaming.

← All data structures