Red Black Trees Top Down Deletion Anlatım

Red-Black Tree Deletion (TOP DOWN)

Red-Black Tree(Kırmızı-Siyah Ağaçlar) üzerinde ekleme ve silme üzerine türkçe makaleler bulamadığım için ve özellikle top-down deletion konusunda ingilizce olarakta kaynak sıkıntısı yaşadığım için anladığım kadarı ile açıklamaya çalışacağım.

Red-Black Tree nedir?

Red-Black tree bir çeşit binary tree'dir. Bildiğiniz üzere binary tree ikili ağaçlar demektir. Peki binary tree varken neden bu tarz ağaç sistemleri oluşturulmuştur? Binary tree tek başına bir yere kadar hayatımızı kurtarıyor. Sayılar rasgele geldiği zaman size O(logn) arama , ekleme ve silme maliyetini garanti ediyor.

Binary tree Visualization

Peki veriler rasgele değilde sıralı gelirse. İkili ağaçlarda eklemeler tek bir kurala göre yapılıyor ve bu kural ağacın tek kuralı. Bu durum sıralı verilerde soruna yol açıyor.

Binary tree Visualization

 Bu tarz durumlarda sağ alt ağaca yapacağınız işlemler O(n) oluyor. İkili ağaçların en büyük özelliği işlemleri O(logn) zaman karmaşıklığında yapabilmemiz. Bu tarz durumları çözmek için ise AVL-SPLAY-RED BLACK TREE ağaçlar geliştirilmiştir. Bu ağaç çeşitleri ağaç üzerinde döndürmeler yaparak ağacı dengeli hale getirmeyi amaçlar.(splay belki biraz daha farklı ama amaç aynı)

Şimdi örnek olması açısından AVL ve Red Black üzerine 1,2,3,4,5,6 değerlerini ekleyelim ve ağaçların yapısına bakalım.

AVL Tree Visualization

Red-Black Tree Visualization

 Gördüğünüz üzere her ağaç kendi yapısına uygun şekilde ağacı daha düzenli hale getiriyor. Bu yazımda sizin Ağaç nedir? İkili Ağaç nedir? AVL nedir? bildiğinizi kabul ederek devam edeceğim ve RB(red-black) Insertion kolay ve anlaşılır olduğundan ve bu konuda yeterli makale olduğunu düşündüğümden o konu üzerine düşmeyeceğim.

Red-Black Tree Top-Down Deletion

Red-Black üzerinde silme işlemi gerçekten yorucu bir süreç. Kural üstüne kural gelirken sadece döndürme değil aynı zamanda renklendirmeler-döndürmeler yapılır. Direk konuya giriyorum.
Öncelikle bu işlemi, yazdığım C# kodu üzerinden anlatacağımı belirtmek isterim. Eğer ingilizcenize güveniyorsanız ve C++/C tercih ediyorsanız buradan devam edebilirsiniz. Gayet güzel bir anlatım ve esprili bir üslubu ile bu sayfa size daha eğlenceli zaman geçirtebilir. Bizimle kalanlar ile devam ediyoruz :)
Silmeye girmeden hemen önce yardımcı fonksiyonlar ile başlamak isterim.

NodeHasChild,IsRed,Move ve TreeDirection enum

NodeHasChild: Bulunduğumuz düğüm herhangi bir çocuğa sahip mi?
IsRed                :Bulunduğumuz düğüm kırmızı mı?
Move                :Eğer bulunduğun düğüm kırmızı ise aranan veriye göre sola yada sağa ilerle. Parent Sibling ve X değerini güncelle geriye hangi tarafa gittiğini belirten değeri dönder.
ROTATIONS :Single ve double rotation işlemlerini halleden referans aktarımı yapılan metodlar.
DelFunc          : Silinecek düğüm ağaçtan koparılmak için kullanılır

Top-Down Deletion temel amacı:

Size kendi anladığım gibi anlatacağım ve bunun %100 literatürde olduğu gibi olduğunu söylemiyorum.
Eğer ağaçta aradığınız veriyi bulacaksanız ilerlemeniz gerekiyor ve bunun için her zaman bir sonraki düğüme geçtiğinizde ulaştığınız düğümün kırmızı yada o düğüme geldiğiniz bir önceki düğümün(ebeveyninin) kırmızı olduğundan emin olacaksınız. Tüm döndürme ve yeniden renklendirme işlemleri bunu garanti etmeyi amaçlıyor. Eğer yanılıyorsam yanlış bildiğim bir şeyi sezerseniz yorumlarda belirtirseniz sevinirim bu sayede daha doğru bir makale olmuş olur.

İlk olarak silmek istediğimiz veriyi arayacağız ve ağaca kök düğümden giriyoruz. İlk önce silmek istediğimiz veri bu mu diye bakıyoruz eğer silinecek veri bulunmuşsa işlemlerde küçük bir nüans eklemesi ile aynı şekilde devam edeceğiz. Silinecek veriyi bulamadığımızı düşünelim ve verimiz kökten küçük olsun sol ağaca gitmemiz gerekiyor ama gitmeden şu kontrolleri yapmalıyız.
Kök kırmızı mı?
Kökün çocuğu var mı?
Kökün kırmızı çocuğu var mı?
RB Tree de kökün asla kırmızı olmayacağını biliyoruz o halde bu durumu ana kök için atlayabiliriz ve sadece kökün çocuğu var mı ve en az bir tanesi kırmızı mı?

Eğer kökün hiç kırmızı çocuğu yok ise kök girişte kırmızı yapılır. İşlemler yapıldıktan sonra kök siyah hale getirilir.


Kök kırmızı yapıldıktan sonra bir sonraki uygun düğüme ilerlenir. Bu düğüm için kontroller yapılır.

Kırmızı ise ilerlemeye devam edeceğiz. Eğer gelinen düğüm kırmızı değilse:
Bu durumu görselleştirelim

 Bu durumda üst düğümün sağ tarafına mı yoksa sol tarafına mı girdiğimiz önem kazanıyor çünkü burada bir döndürme ve yeniden renklendirme mevcut. Eğer burada olduği gibi sağa girmişsek
kırmızı olan kardeşimizi yani S düğümünü P yani ebeveyn düğümün etrafında döndürülür ve P - S arasında bir renk dönüşümü yapılır. Bu işlemin sonucunda oluşacak yapı daha önce bahsettiğimiz ebeveyni kırmızı hale getirme yapısıdır. Yani kırmızı bir düğümden gelmişsek buraya bu ağaç düzgündür gibi bir algı oluşturabiliriz. Ağacın dönmüş hali:

 

Ağacın dönmüş hali bu şekilde ama henüz işlemler bitmedi. İlk olarak kırmızı-kırmızı bozukluğu görüyoruz. İkincisi X e geldiğimiz düğümün kırmızı olacağından bahsetmiştik ama olmadığını görüyoruz. P ve S düğümleri renk değiş-tokuşu yapacak.

Renk değiş-tokuşu yapıldıktan sonra yaşanılan problemlerin çözüldüğünü gördük. Burada bahsetmemiz gereken bir durum var yazdığım kod üzerinde bu işlem rotasyonlar yapılırken hallediliyor. Ama eğer S düğümünün sağında çocuğu var ise bu data yı kaybedemeyiz. S'nin sağına P yi koyduk S nin eski sağını da P nin soluna yazarsak ne ağaç bozulur ne de veri kaybı olur. P > S olduğu için S nin altında kalan tüm değerler P den küçüktür. P nin soluna yazmak ağacı bu sebepten bozmayacaktır. Burada kırmızı P nin solunda siyah P nin sağında kalıyordu ve döndürmeler ona göre yapıldı. S ve X in yerleri tam tersi olursa döndürme ona uygun olacak şekilde yapılır. Bu bizim ağaç üzerinde döndürme işlemi hakkında ne kadar bildiğimiz ile alakalı.

X in çocuklarından ikisi de siyah ise=>

Tüm çocuklar siyah

Eğer X in her iki çocuğuda siyah ise bu durumda kardeşinin çocukları önemlidir. Eğer kardeşinin çocukları da siyah ise un var yağ var şeker var helva yapsana.... :(

Bu durumda işimiz çok kolay:
X ve S => P'nin rengini alır
P de X in eski rengini alır.
Bu örnek üzerinde X ve S kırmızı olacak
P siyah olacak
X artık kırmızı olduğu için uygun çocuğa ilerleyebiliriz.

S nin çocuklarından birisi veya ikisi de kırmızı ise döndür ve yeniden renklendir uygulayacağız. Döndürme işlemleri S nin çocuklarına bağlı
eğer S nin kırmızı olan tek çocuğu var ve bu çocuk iç tarafta ise:

İç çocuklar kırmızı

Bu durumda iç çocuk baz alınarak çift döndürme yapılır ve X=Kırmızı P = Siyah yapılır.

Eğer dış çocuk kırmızı ise yada iki çocuk birden kırmızı ise tek döndürme ve renklendirme yapılır.
İki çocukta kırmızı iken dış çocuk baz alınır çünkü tek döndürme işlemi yapılır daha az işleme tabi tutlmuş olur.

Dış çocuklar kırmızı

Dış çocuklar baz alınarak tek döndürme yapılır ve P=Siyah X,S=Kırmızı ve S nin döndürülen çocuğu =Siyah şeklinde yeniden renklendiriliyor

Aranan düğüm bulunduğunda:

Eğer düğümün sol alt ağacı mevcutsa en büyük değer alınır değilse sağ alt ağacın en küçüğüne bakılır. Eğer bulunduğumuz düğüm herhangi bir çocuğa sahip değilse ve kırmızı ise(ki işlemlerin sonucunda kırmızı yapılacaktır) DelFunc çağrılıp değer ağaçtan kopartılır.
Silme işlemi bu şekilde tamamlanmış olur.

Kodun tam halini buradan alabilirsiniz.Insertion Kodu dahil.
Github hesabıma buradan gidip projelere göz atıp düzeltmeler için önerilerde bulunabilirsiniz.