AVL Ağacı (AVL Tree)

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