Arbre rouge-noir
Arbre binaire de recherche auto-équilibré, à invariants de « couleur » — Rudolf Bayer en 1972, baptisé par Leonidas Guibas (1978). Le choix le plus courant dans les bibliothèques standard.
Cinq règles garantissent une profondeur en O(log n) sans équilibrer aussi strictement qu'un arbre AVL. Résultat : insertion et suppression plus rapides qu'avec un AVL, recherche à peine plus lente. Les opérations exigent des rotations et des recolorations.
C'est le moteur de std::map en C++, de TreeMap/TreeSet en Java, du Completely Fair Scheduler de Linux, d'epoll sous Linux et de nombreuses piles réseau. Concurrents : l'arbre B (pour le disque), l'AVL (charges dominées par la lecture), la skip list (implémentation sans verrou plus simple).