Kendini dengeleyen ikili arama ağacı veri yapısıdır. Orijinal yapı 1972 yılında Rudolf Bayer tarafından “Simetrik ikili B-Ağaçları” olarak oluşturuldu. Fakat 1978 yılında Leonidas J. Guibas ve Robert Sedgewick tarafından yayımlanan makalede bugünkü adını almıştır. Red-black ağaçlar yapı bakımından biraz karmaşıktır. Arama, ekleme ve silme işlemlerini           O(log n) zamanda gerçekleştirirler (ağaçtaki eleman sayısı n). Bazı kuralları vardır: Her düğüm siyah veya kırmızıdır. Kök her zaman siyahtır. Tüm yapraklar siyahtır. Kırmızı düğümün çocukları siyah olmak zorundadır. Seçilen herhangi bir düğümden, altındaki tüm yapraklara olan yolda aynı sayıda siyah düğüm olmak sorundadır.   Diğer tüm kurallar, ikili arama ağacındaki gibidir.     Ekleme ve çıkartma işlemlerinde siyah düğüm sayısına dikkat edilmelidir. Tags: , , , | Categories: Algoritma