Yazan: Şadi Evren ŞEKER
AVL Ağaçları sürekli olarak dengeli olan ikili arama ağaçlarındandır. G.M. Adelson-Velsky ve E.M. Landis tarafından geliştirilmiş olan bu ağaç algoritmasının ismi de bu kişilerin isimlerinin baş harflerinden oluşmaktadır.
Algoritma basitçe, bir düğümün kolları arasındaki derinlik farkı 2 ise bu durumda dengeleme işlemi yapılır. Şayet fark 2′den az ise (yani 1 veya 0) ise bu durumda bir dengeleme işlemine gerek yoktur.
Algoritmanın ağacı dolaşma (traverse) algoritması ikili arama ağaçları ile aynıdır. Ancak ağaca ekleme ve silme işlemleri sırasında ağacın dengesinin bozulması söz konusu olduğu için bu fonksiyonlara ilave olarak derinlik kontrolü eklenmiştir.
Ekleme ve silme işlemlerinde ikili arama ağacının ekleme ve silme işleminin aynısını yaptıktan sonra aşağıdaki dengeleme işlemi yapılır.
Ağaçta ekleme veya silme yapılan her düğüm için:
sol <- Düğümün sol kolunun derinliğini ölç
sağ <- Düğümün sağ kolunun derinliğini ölç
şayet sol - sağ >1
sola dengele
şayet sağ - sol < -1
sağa dengele
Ağaç dengelemesi için ağaçlarda dengeleme konusuna bakabilirsiniz.