Veri Yapıları 2-3-4 Ağaçları

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.

2-3-4 Ağaçları Ekleme

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.

2-3-4 Ağaçları ekleme

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..

2-3-4 Ağaçlar Ekleme Son Durum

Asıl şekilin oklar ile gösterimi ise aşağıda verilmiştir.

Silme İşlemi

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.

2-3-4 ağaçları silme işlemi

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.

2-3-4 Ağaçları silme işlemi

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.

2-3-4 ağaçları kök silme işlemi

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.

2-3-4 ağaçları ebeveyn silme

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.

2-3-4 Tree ağacı silme işlemleri

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:

2-3-4 ağaçları tekli ebeveyn silme

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.

2-3-4 ağaçları tek ebeveyn silme işlemi sonucu

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.

Son iki kural için örnek ekleyemedim. Umarım anlaşılmıştır. Sorularınızı yorum yaparak sorabilirsiniz.

Bir cevap yazın