Kırmızı-siyah ağaç
“Renk” değişmezleriyle kendini dengeleyen ikili arama ağacı: Rudolf Bayer 1972, adı Leonidas Guibas’tan (1978). Standart kütüphanelerde en sık seçilen yapı.
Beş kural, AVL kadar sıkı dengelemeden O(log n) derinliği garanti eder. Sonuç: AVL’den daha hızlı ekleme/silme, biraz daha yavaş arama. İşlemler döndürme ve yeniden renklendirme gerektirir.
C++ std::map’i, Java TreeMap/TreeSet’i, Linux Completely Fair Scheduler’ı, Linux epoll’u ve birçok ağ yığını uygulamasını çalıştırır. Rakipler: B-ağacı (disk için), AVL (aramanın ağır bastığı yükler), Skip list (kilitsiz uygulaması daha basit).