AVL Tree Nedir?

Bir AVL Ağacındaki her düğüm kendi yüksekliğini takip eder: bir yaprağa giden en uzun yoldaki kenar sayısı. Bir yaprağın yüksekliği 1'dir ve boş bir alt ağaç 0 yükseklik olarak sayılır. Bir düğümün iki çocuğunun yüksekliğinden, o düğümün denge faktörünü hesaplayabilirsiniz: height(left) - height(right).

Bir düğüm, denge faktörü -1, 0 veya 1 olduğunda dengelidir. AVL Ağacının kuralı basittir: her bir düğüm her zaman dengeli kalmalıdır. Bir ekleme veya silme işlemi bir düğümün denge faktörünü 2 veya -2 değerine ittiğinde, ağaç bir rotasyon gerçekleştirir: arama ağacı sıralamasını bozmadan dengeyi sabit sürede geri yükleyen birkaç işaretçinin yerel olarak yeniden düzenlenmesi.

Dört rotasyon durumu vardır (sol-sol, sağ-sağ, sol-sağ, sağ-sol), ancak bunların hepsi iki temel yapı taşına indirgenir: tek bir sol rotasyon ve tek bir sağ rotasyon. Önümüzdeki birkaç derste her ikisini de sıfırdan inşa edeceksiniz.