Merhaba arkadaşlar, veri yapıları derslerinde anlatılan bir tür ağaç çeşidi olan 2-3-4 Tree ile ekleme silme işlemlerini anlatacağım.
Çok yollu ağaçlar olarak tanımlanan B Tree’lerin devamı gibidir. Fakat ben bu yazımda direkt olarak 2-3-4 ağaçlarının kurallarını verip anlatıma geçeceğim.
Bu ağaçlar Binary Tree gibi derinlik öncelikli değil de genişlik öncelikli ağaçlardır.
1 Tane kök düğümü varsa 2 tane yaprağı olabilir.
2 Tane kök düğümü varsa 3 tane yaprağı olabilir.
3 Tane kök düğümü varsa 4 tane yaprağı olabilir.
Adını bu kuraldan almaktadır.
2-3-4 Tree Ekleme İşlemi
Yaprak içerisinde en fazla 3 düğüm olabilir. 4. Düğüm geldiğinde ortadaki düğüm bir üst sıraya gitmesi gerekir.
1’den 10’a kadar olan sayıları eklemeyi excel üzerinde adım adım göstermeye çalıştım. Ok kullanmadım anlayacağınızı düşünüyorum.
1’den 5’e kadar eklemeyi yukarıda yaptım. Şimdi 6’yı eklediğimizde 4 sayısı bir üste çıkacak. 3’de ayrı bir yaprak olacak. Daha sonra 7’yi ekleyerek devam ediyoruz.
8 eklendiğinde 6 üst köke geçiyor. 9 normal ekleniyor. Şimdi ise 10 eklediğimizde 8 üstte çıkacak yer bulamıyor. Bu yüzden kökün ortasındaki sayı (4) bir üste çıkmış olacak. Hemen bakalım son görünüme..
Asıl şekilin oklar ile gösterimi ise aşağıda verilmiştir.
Silme İşlemi
[the_ad id=”1292″]
Silme işleminde de bazı kurallar var yine. Eğer yukarıda verdiğimiz genel kurallarda bir sıkıntı yok ise sayı direkt silinebilir.
Yukarıda 90’ı silmek istediğimizde direkt olarak silebiliriz. 85|95 bir yaprak olarak kalacaktır.
Eğer alt yapraklardan birisinde minimum düğüm sayısı bozulur ise sol çocuk ile ebeveyn arasında düzenleme işlemi yapılır.
Yukarıdaki ağacın aynısında 25 değerini silmek istediğimizde 12 ile kök yer değiştirir. 20 aşağı aşağı iner. Ve 25 silinir.
Eğer silinen değer kök ise ve çocukları da minimum sayıdan büyük ise, soldaki en büyük çocuk köke taşınır. Yukarıdaki örnekte 40’ı sildiğimizde aşağıdaki gibi bir ağaç oluşacaktır.
Eğer çocukları olan bir düğüm silinecek ise bu sefer de düğümü fazla olan yapraktan bir düğüm alır. Örnek olarak son yukarıdaki ağacımızdan 60 değerini silmek istediğimizde 55 değeri yukarı çıkarılır ve silinir. Son olarak ağacımız aşağıdaki gibi görünecektir.
Minimum kapasitenin altına düştüğünde ise ebeveyn ve çocuklar birleştirilir. Örnek olarak yukarıdaki örnekteki 20 değerini silmek isteidiğimizde 12 değeri aşağı iner ve 10 ile birleştirlir. Ağacımız aşağıdaki gibi görünecektir.
12 değeri kök değildir. Sadece aşağıya geldiğini belitmek amaçlı kullanılmıştır.
Eğer çocukları olan ve düğüm sayısı da tek değere sahip ise kardeşi ile birleştirilir. Örnek olarak aşağıdaki ağaç verildiğinde:
Buradan 85 değerini silmek istediğimizde, 12 37 ve 50 sayıları birleştirilir. Sonuç aşağıdaki gibi bir ağaç olmaktadır.
Eğer ebeveyn düğüm silinecek ve tek ise, kardeşi tek değilse döndürme işlemi yapılır. Kardeş düğüm köke çıkar. Kökde kendisinden küçük olan düğüm var ise aşağıya silinecek olan düğümün yanına iner ve silinmesi istenilen düğüm silinir.
Eğer silinecek yaprak düğümün ebeveyni ve kardeşi tek değere sahip ise ebeveyn, kardeş ve çocuk düğümler birleştirilir.
[the_ad id=”1292″]
Son iki kural için örnek ekleyemedim. Umarım anlaşılmıştır. Sorularınızı yorum yaparak sorabilirsiniz.
