AVL Trees (AVL Ağaçları)

Merhaba arkadaşlar,

Bugünkü konumuz aynı zamanda Binary Search Tree sınıfına dahil edilebilecek olan AVL Trees. AVL ismini, mucitlerinden almış (mucit kelimesi uygun olmadı sanki?). Adelson-Velskii-Landis. Binary Search Tree'yi anlatırken bahsetmiştik, verilerin geliş sırasına göre şekillenen bir yapısı vardı BST'nin. Bu yüzden derinlik çoğu zaman alıp başını gidebilirdi(bir sürü alt node ortaya çıkar). İşte AVL Tree tam da bu noktada devreye giriyor. Dengeleme işlemi için geliştirilmiş olan bu ağaç yapısı, performansı arttırmak için sürekli olarak kendisini yeniden düzenler(re-organize). Yani bir düğümün(node) alt ağaçlarının yükseklikleri(derinlikleri) yaklaşık olarak aynıdır, demekte bu yöntem. Bu yüzden bu yönteme "height balanced tree" de denmektedir. Daha önce de belirttiğim gibi, bir düğümün sağında ve solunda kalan ağaçlarının derinliği yaklaşık olarak aynı değilse, yeniden düzenleriz.

AVL Tree metodunu kullanabilmek için balanced factor sayısını bulmalıyız.

balanced factor=(sağ alt ağacın derinliği) - (sol alt ağacın derinliği)

balanced factor değeri 0, +1, -1 değerleri çıkarsa sorun yok. Bu üç değer dışında bir sonuçla karşılaşırsak, o ağacı yeniden düzenleriz.

Yeniden düzenleme işi de dört adet şablona göre yapılır. Bu şablonlar olası dengesizlikleri ve nasıl çözüleceklerini söylerler. Yani bizim ağacımız hangi şablona uyuyorsa, çözümü de o şablona göre yapacağız.

1. Şablon

Yukarıdaki şablonda X ve Y birer node. A,B,C ise birer alt ağacı temsil etmektedirler. A ağacının derinliği h olsun. B ağacınınki de h, C ağacının derinliği ise h+1 olsun. Balanced factor'u hesaplayacağız. Y düğümü için hesaplarsak= sağ  alt ağacın derinliği - sol alt ağacın derinliği. (Sağ alt ağacı C. Sol alt ağacı ise B.)

Bu durumda= (h+1) - (h)= +1

Y düğümünün derinliği +1.

Şimdi X düğümü için bakalım. solunda bir alt ağaç var. A alt ağacının derinliği h demiştik. Sağ tarafını da anlarsanız bu konunun büyük kısmını bitirirsiniz. :) Sağ tarafta Y düğümü var. Y düğümünün altında B ve C vardı. Burada B'nin h, C'nin ise h+1 derinliği var. Yani Y düğümünün altında en fazla h+1 derinlikte ağaç var. Bir de kendisini katarsak(Y düğümünü), X düğümünün sağ tarafındaki derinlik h+2 olur. Tekrar anlatayım, sol tarafta A alt ağacının derinliği=h.    Sağ tarafta Y bir düğüm olduğu için derinliği +1, bir de altındaki alt ağacın derinliği h+1. Toplarsanız, h+2 de sağ tarafın derinliği olur. 

X için balanced factor ise=(h+2) - (h) = +2

Gördüğünüz gibi 0,-1,+1 dışında bir değer çıktı. Yeniden düzenleme yapmak durumundayız. 

Burada anlatılmak isteneni kabaca şöyle tarif edelim. Ağacınızda balanced factoru +2,+1 şeklinde düğüm varsa, ağacınızın iyileştirmesi aşağıdaki gibidir:

Bu da birinci şablonun çözümü olur. A ve B'nin derinlikleri h idi. X'in balanced factor'u 0 oldu. Y'ye gelelim. Sağ tarafında C'nin derinliği h+1 idi. Y'nin sol tarafında X'in derinliği  +1(çünkü X sadece bir düğüm), h derinliğine sahip alt ağaçları da var, ki onların derinliği de h. Toplamda h+1 de sol tarafın derinliği. Böylelikle Y'nin balanced factor'u= (h+1) - (h+1) = 0 olur.

Diğer şablonlar da aynen böyle. Diğer şablonlarda sadece derinlikleri yazacağım, açıklamaya gerek olmadığını düşünüyorum artık.

2.Şablon
X ve Y birer düğüm.
A, B, C birer alt ağaç. A ağacının derinliği h+1 olsun. B ağacınınki de h, C ağacının derinliği ise h olsun. Kısacası, düğümlerinin balanced factor'u -2(X) ve -1(Y) olan ağacınız varsa, bu şablonun çözümü sizin için.

Çözümü ise:

 3.Şablon
 X, Y ve Z birer düğüm.
A, B, C, D birer alt ağaç. B ağacının derinliği h-1 olsun. A, C ve D ağaçlarının derinliği ise h olsun. Kısacası, düğümlerinin balanced factor'u +2(X), -1(Y) ve +1(Z) olan ağacınız varsa, bu şablonun çözümü sizin için.

 Çözümü ise:

4.Şablon

 X, Y ve Z birer düğüm.
A, B, C, D birer alt ağaç. C ağacının derinliği h-1 olsun. A, B ve D ağaçlarının derinliği ise h olsun. Kısacası, düğümlerinin balanced factor'u -2(X), +1(Y) ve -1(Z) olan ağacınız varsa, bu şablonun çözümü sizin için.

Çözümü ise:

Ağacınız hangisine uyarsa, onu baz alırsınız. Tüm şekilleri az önce tek tek elle çizdim, ki zaten beni tanıyanlar bozuk ve yamuk şekilllerden hemen anlamıştır. :)
Derinliklere ve balanced factor'lere dikkat ederseniz, çok çok kolay bir yöntemdir.

Görüşmek üzere..