Merhaba arkadaşlar bu yazımızda kırmızı siyah ağaçlarda silme işlemini ele alacağız.Önceki yazımzıda ekleme ve arama işlemlerinden bahsetmiştik. Önceki yazımızı incelemek için tıkla. Bu yazımızda ise kırmızı siyah ağaçlar üzerinde silme işlemi nasıl yapılır bunlardan bahsedeceğiz.
Öncelikle her bir kuralı Tek tek verirsek bu daha faydalı olacaktır. Daha sonra kurallar için detaya inebiliriz. Kırmızı siyah ağaçlarda ekleme işlemi yaparken kırmızı rengi yapraktan köke doğru(bottom-up) şeklinde taşımıştık. Bu sefer kırmızı siyah ağaçlarda silme işlemi uygularken ise kırmızı rengi kökten yaprağa yani silinecek düğüme(up-bottom) taşıma işlemi yapacağız.
Başlangıç Adımı!!
Bütün adımlara başlamadan önce uygulamamız gereken kesin bir adım vardır. Silinecek düğüm kendi ağacının SOL EN BÜYÜK veya SAĞ EN KÜÇÜK düğümü ile yer değiştirilir. Bu yer değiştirme işleminde renkler taşınmaz yalnızca sayısal değerler taşınır bunu Başlangıç adımı olarak kabul edebiliriz.
Adım1-A1) EĞER KÖKÜN HER İKİ ÇOCUĞU DA SİYAH İSE BU ADIM UYGULANIR!
Uygulanışı: Kök kırmızı yapılır, X uygun düğüme taşınır, Adım 2 ‘ye geçilir.
Adım1-A2)Kökün her iki çocuğu siyah değil ise bu adım uygulanır!
Uygulanışı: X=P olarak ayarlanır ve Adım2-B ye geçilir.
Adım2) P’nin KIRMIZI X ve S nin siyah olduğu durumlarda işletilir.
Uygulanışı: X uygun çocuğa taşındıktan sonra iki farklı ihtimal mevcuttur. Bu durumda iki yeni kural aşağıdaki gibi oluşur.
Adım2-A) X’in çocukları (A ve B) siyah olduğu durumda uygunlanır.
Uygulanışı: Bu durumda S’nin çocuklarına göre döndürme ve renklendirme işlemi aşağıdaki alt kurallara göre uygulanır.
Adım2-A1)S’nin her iki çocuğu siyah ise uygulanır!
Uygulanışı: P, X ve S yeniden renklendirilir.
Adım2-A2)S’nin sol çocuğu kırmızı ise uygulanır!
Uygulanışı: Önce Çift döndürme yapılır. Daha sonra P,X ve S yeniden renklendirme işlemi uygulanır.
Adım2-A3) S’nin sağ çocuğu kırmızı ise uygulanır!
Uygulanışı: Tek döndürme yapılır. P, X ve S yeniden renklendirilir.
NOT: Eğer S’nin her iki çocuğu kırmızı ise, iç veya dıştakine göre işlem yapılabilir sonucu etkilemez.
Adım2-B)Bir öncekinden tek farkı X’in herhangi bir çocuğunun kırmızı olma durumudur. Bu adım yalnızca X’in çocuklarından birinin kırmızı olma durumunda uygulanır.
Uygulanışı: Bu adımda X silinecek düğüme doğru direk taşınır. Bu işlem sonucunda iki ihtimal bulunur. Yeni X’in siyah veya kırmızı olması.
Adım2-B1) Bu adım eğer yeni X kırmızı ise uygulanır!!
Uygulanışı: Herhangi sorun olmaz, taşıma işlemi devam eder.
Adım2-B2)Bu adım eğer yeni X siyah ise uygulanır!
Uygulanışı: S düğümüne P’nin etrafında bir tur çevirme işlemi uygulanır. Çevirme işleminin ardından P ve S yeniden renklendirilir. Tekrar Adım2’ye dönülür.
Adım3)Silinecek düğüme ulaşıldıysa silme işlemi gerçekleştirilir.
Adım4) Kök tekrar siyah yapılır.
Herhangi bir kırmızı-Siyah ağaç(red black tree) için bu adımları eksiksiz uygularsanız hatasız bir şekilde silme işlemini bitirebilirsiniz. Yine de işlemleri kontrol etmek istiyorsanız buradan simulatöre gidip işleminizi test edebilirsiniz
Soru veya yorumlarınızı aşağıdan bana bildirebilirsiniz.
Teşekkürler.
