Árbol rojo-negro
Árbol binario de búsqueda autoequilibrado con invariantes de "color" — Rudolf Bayer, 1972; el nombre es de Leonidas Guibas (1978). La opción más habitual en las bibliotecas estándar.
Cinco reglas garantizan una profundidad O(log n) sin equilibrar tan estrictamente como un AVL. Resultado: inserción y borrado más rápidos que en un AVL, a cambio de búsquedas algo más lentas. Las operaciones requieren rotaciones y recoloreos.
Está detrás de std::map en C++, TreeMap/TreeSet en Java, el Completely Fair Scheduler de Linux, epoll de Linux y muchas implementaciones de pila de red. Rivales: el árbol B (para disco), el AVL (cargas con muchas lecturas) y las skip lists (más fáciles de implementar sin bloqueos).