Árbol rojo-negro
Red-black tree
- Fecha
- 1978 · fiabilidad media
- Lugar
- Xerox PARC, Palo Alto, California, Estados Unidos
- Autoría
- Leonidas J. Guibas y Robert Sedgewick, a partir del árbol-B binario simétrico de Rudolf Bayer
- Ámbito
- Saber y símbolos
⚠️ Dato en discusión: las fuentes no coinciden.
Qué es
Guibas y Sedgewick formalizaron, en su artículo «A Dichromatic Framework for Balanced Trees», el árbol binario de búsqueda autoequilibrado hoy llamado rojo-negro, derivado del árbol-B binario simétrico que Bayer había descrito en 1972.
Wikidata atribuye el hito sólo a Rudolf Bayer, pero su estructura de 1972 (el «árbol-B binario simétrico», hoy llamado árbol 2-3-4) es el precursor directo; el árbol rojo-negro tal y como se conoce hoy lo formalizaron Guibas y Sedgewick en 1978.
A qué dio paso
- Uso del árbol rojo-negro en estructuras de datos estándar (mapas y conjuntos de C++, TreeMap de Java)
- Planificador de procesos «Completely Fair Scheduler» del núcleo Linux