Bilgisayar bilimlerinde kullanılan bir veri yapısıdır (data structures). Özel bir ağaç yapısıdır ve amaç ağacı sürekli olarak dengeli (balanced) tutmaktır.
Ağaçtaki düğümlere (nodes) isim olarak 2 veya 3 ismi verilebilir. Her düğüm aldığı isme göre farklı işleme tabi tutulur. Düğümlerin isimlendirilmesi aşağıdaki şekilde yapılır:
2 düğümleri (2 nodes) : 2 adet çocuğu ve bir veri elemanı bulunan düğüm yapısıdır
3 düğümleri (3 nodes) : 3 adet çocuğu ve iki veri elemanı bulunan düğüm yapısıdır.
2-3 Ağacına Ekleme işlemli
Ağaca eklemeyi bir örnek üzerinden adım adım görelim. Ağacımıza ekleyeceğimiz sayılar aşağıdaki şekilde veriliyor olsun:
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, aslında aşağıdaki gibi bir yapı elde edilir:
Ancak ne yazık ki 2-3 ağaçlarında, 3 adet değeri tek bir düğümde bulundurma şansımız yoktur. Bu yüzden yukarıdaki bu hayali yapı bölünerek aşağıdaki şekle geçilir ve 3 adet 2 tipinde düğümümüz olur:
Yeni gelen değerimiz 52’dir:
Yukarıdaki yeni şekilde, gelen 52 değeri, kök düğüm olan 50’den başlanarak ağaçta ufak bir dolaşmaya sebep olur. Öncelikle 50’den küçük olduğu için bu düğümün sağına sonra da 97’den küçük olduğu için bu düğümün soluna yerleştirilir.
52 değerinin, 50 değerinin sağına yerleştirilmemesinin sebebi, bu durumda ağaçta iki veri ve iki çocuk bulunan aşağıdaki hayali ağacın oluşmasıdır:
Yukarıdaki bu hayali ağaç ne yazık ki 2-3 ağaçlarında yer almaz. Tekrar hatırlatacak olursak 2-3 ağaçlarında 2 düğümlerinin 2 çocuk ve bir verisi, 3 düğümlerinin ise 3 çocuk ve 2 verisi bulunur. Yukarıdaki kök düğüm ise 2 veri ve 2 çocuk bulundurmaktadır. Bu durum kabul edilemez.
Yeni eklenen değerimiz 19:
Yukarıdaki bu yeni ağaç yapısı, bir önceki adımda açıklandığı gibi, 50’nin yanına yeni bir veri eklenememesinden dolayı, 50’nin solundaki düğüme eklenmesi sonucunda elde edilmiştir.
Sıradaki eklenecek olan veri 11’dir. Eklenmiş halini görmeden önce, hayali olarak ağaçta olması beklenen adımları açıklayalım. Öncelikle verinin eklenmek isteneceği yer, 50 değerindeki kök düğümünün soludur.
Yukarıdaki hayali ağaç, ne yazık ki 2-3 ağaçları tarafından kabul edilemez. Dolayısıyla üç veri içeren bu düğümü tek başına ele aldığımızda (ki aynı durum, örneğimizde 97 eklenirken de yaşanmış ve 3 adet veri yan yana elde edilmesin diye 3 adet 2 tipinde düğüme dönüştürülmüştü) bölünme işlemi gerçekleştirilir:
Yukarıdaki bu alt ağacı, bir önceki ağacımız ile birleştirirsek:
Elde ettiğimiz yeni ağaç, yukarıdaki şekilde iki ağacın birleştirilmiş hali olur.
Son olarak ekleyeceğimiz değer 111 olsun. Bu değer eklendiğinde ağaçta bir zincirleme reaksiyon oluşur ve birden fazla düğümün yukarıya doğru bölünmesi gerekir. Öncelikle 111 değeri 50’den büyük olduğu için, ağaçta 50’nin sağındaki gösterici (pointer) tarafından gösterilen düğüme yönlendirilir ve sanki aşağıdaki hayali ağacın oluşmasına sebep olur:
Elbette yukarıdaki bu 3 veriyi yan yana tutan düğümü kabul edemeyeceğimiz için bu düğümü bölüyoruz:
Bu sefer kök düğümdeki 3 veriyi kabul edemeyeceğimizden dolayı, kök düğümü de bölüyoruz:
Sonuçta, yukarıdaki ağaç 2-3 ağacı olarak bütün değerlerin eklendiği ağaçtır. Buradaki son bölünmeden sonra toplam 7 adet 2 tipinde düğüm elde edilmiştir. Ayrıca yukarıdaki ekleme işlemleri boyunca her adıma bakıldığında ağacın dengeli bir ağaç olduğu (bütün yaprak düğümlerinin (leaf nodes) aynı seviyede olduğu ) görülebilir.
Aslında yukarıdaki isimlendirmeler, B-Ağacının (B-Tree) özel bir şekli olarak düşünülebilir. Yani, düğüm boyutu 2 olan bir b-ağacında, her düğümde ya iki ya da tek eleman bulunacak ve bulunan eleman sayısının bir fazlası kadar çocuk bulunacaktır.
2-3 Ağaçları, AA ağaçlarının (AA-trees), eş şekillisi (isometry) olarak düşünülebilir.
