2-3-4 Ağaçları (2 3 4 trees)

Yazan : Şadi Evren ŞEKER

2-3-4 ağacı, B-ağaçlarının (B-Trees) özel bir halidir. Bu ağacın özelliği, düğüm boyutunun (node size) 3 ile sınırlı olmasıdır. Ağaç ayrıca sürekli olarak dengeli bir ağaç garantisi verir (balanced tree). 2-3-4 ağaçları, kırmızı siyah ağaçlarının (red-black trees) , eş şekillisi (isomorphic) olarak da düşünülebilir.

2-3-4 ağacının ismi, ağaçtaki düğümlerin değişik durumlarda değişik numaralar almasından kaynaklanmaktadır. Yani bir düğüm 2,3 veya 4 durumunda olabilir. Bu durumlara göre farklı uygulamalar söz konusudur.

2 düğümü: 2 adet çocuk düğümü gösteren gösterici (pointer) ve bir veriden oluşur

3 düğümü: 3 adet çocuk düğümü gösteren gösterici (pointer) ve iki veriden oluşur

4 düğümü: 4 adet çocuk düğümü gösteren gösterici (pointer) ve üç veriden oluşur

Ekleme işlemini bir örnek üzerinden anlamaya çalışalım

50, 27, 97, 52, 19, 11, 111

Bu sırayla verilen değerleri sırasıyla ağaca ekleyelim:

İlk sayı olan 50’nin eklenmesi sonucunda ağaçta tek bir düğüm ve bu düğümde tek bir veri bulunuyor. Bu tip düğüme 2 düğümü ismi verilmektedir ve iki çocuğu da boştur (null).

İkinci eklenen değer 27’dir. Ağacımızda tek düğüm bulunduğundan ve bu düğüm 2 tipinde olduğundan, düğümde yeni değeri alacak yer bulunmaktadır. Bu yere yeni gelen değer yerleştirilir. Elbette düğümlerin içerisinde sıra bulunması gerektiği için, 27 değeri, 50 değerinin soluna yerleştirilmiştir. Bu kural bundan sonraki ekleme işlemlerinde de geçerli olacaktır. Yani düğüm içerisindeki değerler kendi aralarında sıralı olacak ve herhangi bir değerin solundaki çocuklarının değeri, kendi değerinden küçük ve sağındaki değeri kendi değerinden büyük olacaktır.

Ardından gelen ekleme değeri, 97’dir. Bu değer düğüme eklenince, aşağıdaki gibi bir yapı elde edilir:

Yukarıdaki bu yeni yapı, bizim 2-3-4 ağacımızdaki 4 tipindeki yapıdır ve kabul edilebilir bir durumdur. Ancak bir sayı daha eklenince yapı bozulacaktır. Nitekim sıradaki sayımız olan 52’nin eklendiğini düşünelim:

Şimdiye kadar öğrendiklerimize göre, yukarıdaki gibi bir yapı olması beklenir. Ancak yukarıdaki yapı 2-3-4 ağacı tarafından kabul edilemez (2,3 veya 4 tipinde bir düğüm değildir). Dolayısıyla bu yapının kabul edilir bir şekle indirgenmesi gerekir.

Yukarıdaki yeni şekilde, ağaç 50 ve 27 değerlerini taşıyan iki adet 2 tipinde düğüm ve bir adet 52 ve 97 değerlerini taşıyan 3 tipinde düğüme indirgenmiştir. Bu düğümlerin tamamı 2-3-4 ağacı tarafından kabul edilir düğümlerdir.

Ekleme işlemine 19 sayısı ile devam edelim.

Yukarıdaki şekilde görüldüğü üzere, 19 sayısı, 50’den küçük olduğu için kökteki bu değerin solundaki düğüme yerleştirilmiştir.

11 sayısı eklendikten sonra, bu sayı da daha önceden olduğu gibi, 50’nin solundaki düğüme sıralı olarak eklenir.

Benzer şekilde 111 sayısının eklenmesi de kök değerin sağına yapılır:

Son olarak ağacın 3 düğümü olarak taşıyamayacağı bir örneği göstermek için, örneğin 120 sayısını ağaca eklemeye çalışalım:

Normalde 120 sayısının ekleneceği yer, yukarıdaki şekilde gösterildiği gibi ağacın sağ koludur. Ancak bu durum 2-3-4 ağacı tarafından kabul edilemez çünkü herhangi bir düğüm yapısına uygun değildir.

Çözüm olarak daha önceden 52 sayısının eklendiği örnekte olduğu gibi düğümleri indirgiyoruz.

Bu işlemden sonra kök düğümünü güncelleyerek sonuçta çıkacak olan ağacı elde ediyoruz

Ağacımız son halinde 2-3-4 ağacı kurallarına uygun düğümlerden oluşmaktadır.