Merhaba Arkadaşlar,
Bu yazımızda C# üzerinde nesne tabanlı programlama kullanarak red-black tree kodlarını oluşturacağız ve inceleyeceğiz.
Bu yazımızın fazla uzayıp karmaşıklaşmaması için Kırmızı-Siyah ağaçların üzerinde ekleme işlemi , arama işlemi ve Kırmızı Siyah Ağacın Kurallarından bahseceğim. Uygulamaya başlamadan önce Red-Black Tree hakkında bilgi verelim. Kırmızı – Siyah ağaçlar birer dengeli ağaç tipidir. Algoritmik çalışma zamanı olarak inlcelendiğinde silme,ekleme,oluşturma gibi işlemlerin maliyeti (En kötü Durum için) O(logn)’dir. Yapı olarak neredeyse Full Binary Tree ile benzerlik gösterirler. Oluşturmak için özel kuralları vardır örnek olarak verecek olursak:
•Ağaçtaki her düğüm kırmızı ya da siyahtır
•Kök düğümher zaman için siyahtır.
•Bütün yaprak düğümler siyahtır
•Herhangi bir kırmızı düğümün bütün çocukları siyahtır.
•Herhangi bir düğümden, yaprak düğüme kadar gidilen bütün yollarda eşit sayıda siyah düğüm bulunur.
Örnek olarak Bir Kırmızı-Siyah ağaç verecek olursak:
Ekleme ya da silme işlemleri için gerekli bazı kurallar bulunmaktadır. Ekleme Olayından başlayalım.
Kırmızı- Siyah Ağaçlarda Düğüm Ekleme
İlk esnada belirttiğim gibi ağacın genel yapısı Full Binary Tree’ye benzetilebilir yani bir düğümden sonra gelecek olan değer kendinden küçük ise kendisinin soluna büyükse kendisinin sağında yer alacaktır. Bu adımdan sonra renklendirme işlemi olacaktır. Bunun için üç farklı kural bulunmaktadır.
•Kök düğüm her daim siyahtır.
•Ağacın yüksekliğini kontrol ederken mevcut düğümden en alta kadar olan siyah düğümler sayılarak kontrol edilir.
•Kırmızı bir düğümün Kırmızı bir çocuğu olamaz.
Yukarıdaki üç kuraldan herhangi birinin ihlali olması halinde, yapılacak iki farklı işlem bulunmaktadır; renk değiştirme veya döndürme.
Renk değiştirme durumunu daha iyi kavramak için, kırmızı bir düğümün altına bir değer eklenme durumunu örnek gösterelim. Mesela aşağıdaki gibi bir tabloya 15 değeri eklenecek olursa;
Mevcut durumu inceleyecek olursak, 15 değeri, 10 düğümünün sağ tarafına denk gelecek ve Kırmızı bir düğümün çocuğu kırmızı olarak sorun oluşturacaktı. Bu durumun oluşması halinde “10” değerini içeren düğümün kardeşine bakıyoruz, eğer kardeşi de kendisi ile aynı renkte yani Kırmızı ise , RENK DEĞİŞTİRME işlemi uygulanıyor, 10 ve 1 numaralı düğümlerin rengi Kırmızıdan Siyaha dönüyor. Böylece hem siyah dengesini korumuş hemde kural ihlalini ortadan kaldırmış oluyoruz.
Bir sonraki düzensizlik giderme işlemi Döndürme. Eğer daha önce incelediyseniz döndürme işlemi AVL ağacında alıştığımızın aynısı. LL-RR (iç) dönüşümler ve LR-RL (dış) dönüşüm olarak iki farklı dönüşüm tipi bulunuyor. Döndürme işlemini yaptıktan sonra siyah dengesini korumak için yeniden renk sayımı yapıp, renklendirme işlemini tekrar etmemiz gerekebilir. Döndürme işlemi için aşağıdaki örneği verebiliriz.
Yukarıdaki örnekte eklenen “3” değeri “Kırmızı bir düğümün kırmızı çocuğu olmaz” kuralını ihlal ediyor. Bu durumda “2” numaralı düğümün kardeşine baktığımızda “nil” düğümler daima siyahtır kuralına dayanarak kardeşinin siyah olduğunu söyleyebiliriz. Bu durum oluştuğunda döndürme işlemi gerçekleşmektedir, örnekteki döndürme işlemi RR(Sağ-Sağ) dönüştürme işlemi olduğunu göz önünde bulunduralım. Bu durum hem siyah dengemizi korumaya hemde değer dengemizi korumaya yarıyor.
Döndürme işlemlerinin tamamını aşağıdaki gif ile özetleyebiliriz.
Kırmızı-Siyah Ağaçlarda Döndürme İşlemi.
Bir önceki durumda RR(iç) durumu incelemiştik. Bu adımda herhangi bir dış durumun denge durumunu inceleyelim. Örnek olarak aşağıdaki ekleme işlemini verebiliriz.
Yukarıdaki ağaca “32” değeri eklendiğinde “Kırmızı düğümün kırmızı çocuğu olamaz” kuralını ihlal ettiğinden bir kuralsızlık durumu oluşmaktadır. ” 35″ değerine sahip düğümün kardeşi de siyah olduğundan dolayı döndürme işlemi yapılacaktır. Bu düzensizlik türü RL(Sağ-Sol) tipi olduğundan gerekli döndürme işlemi uygulanır. Önce 35 ve 32 değerleri arasında döndürme uygulanır. Bir sonraki adımda son döndürme işlemi olan 32 ve 30 değerleri arasında döndürme uygulanır. Döndürme işlemi tamamlandığında bozulan renk dengesini gidermek amacı ile “32” değerine sahip düğüm üzerinde renk değiştirme işlemi uygulanır.
Kırmızı-Siyah Ağaçlarda Düğüm Arama
Kırmızı Siyah Ağaçlarda düğüm arama işlemi Full Binary Tree ile aynıdır. Değerleri kurallı bir ağaç olduğundan aranan düğümü bulana kadar; aranan değer üzerinde durulan düğümden büyükse düğümün sağ çocuğuna, aranan değer üzerinde durulan düğümden küçüksa sol çocuğuna bakılır.
Kırmızı-Siyah ağaçlar ile ilgili bu yazımızın şimdilik sonuna geldik. Bu konu ile bir sonraki yazımızda Silme işleminden bahsedeceğiz.
Konu ile ilgili soru ve görüşleriniz için yorum kısmını kullanabilir veya mail atabilirsiniz. Teşekkürler.
