Red-black tree
Árbol rojo-negro
- Date
- 1978 · confidence medium
- Place
- Xerox PARC, Palo Alto, California, United States
- Credited to
- Leonidas J. Guibas and Robert Sedgewick, building on Rudolf Bayer's symmetric binary B-tree
- Field
- Knowledge & symbols
⚠️ Disputed: the sources disagree.
What it is
Guibas and Sedgewick formalized, in their paper "A Dichromatic Framework for Balanced Trees," the self-balancing binary search tree now called red-black, derived from the symmetric binary B-tree Bayer had described in 1972.
Wikidata attributes the item to Rudolf Bayer alone, but his 1972 structure (the "symmetric binary B-tree," today called a 2-3-4 tree) is the direct precursor; the red-black tree as known today was formalized by Guibas and Sedgewick in 1978.
What it led to
- Use of red-black trees in standard data structures (C++ maps/sets, Java's TreeMap)
- The Linux kernel's Completely Fair Scheduler