 |
| AVL Ağacı |
AVL Tree kavramını ilk olarak duyduysanız AVL Ağacı nedir sorusunu sormuş olmanız muhtemeldir. AVL Ağacı ikili arama ağacıdır. AVL'nin temel özelliği ekleme ve silme işlemleri sırasında ağaçta oluşacak olan dengesizlik durumlarında dengeleme işlemi yapmasıdır. Bu dengeleme işleminin sorgusuna avl balance factor denilir.
AVL Balance Factor Nedir?
AVL ağaçlarında düğümlerin derinlikleri arasındaki fark 1'den fazlaysa dengeleme işlemi yapılmalıdır. AVL algoritması bu dengeleme işini yapar. Dengeleme işini yapan algoritmaya balance factor denilir. Balance factor yalnızca yükseklikler arası fark 1'den fazlaysa devreye girer. Şayet yükseklik farkı -1,0,1 ise devreye girmez.
AVL Ağacı Yüksekliği Nedir?
14
/ \
9 15
/ \
7 8
/
5
Yukarıdaki ağaca bakarsak, sol tarafın toplam derinliği 3 birim, sağ tarafın toplam derinliği 1 birimdir. Aşağıya inme durumu temel kriterdir. Yukarıdaki ağaç AVL ağacı yapısına uymaz. Dengeleme işlemi gerektirir. Neden? Çünkü derinlik farkı 1'den büyüktür.
AVL Algoritması Nasıl Uygulanır?
AVL Ağacı algoritması ağaca düğüm eklerken ya da silerken uygulanır. Aslında bu işlemlerin normal bir ağaca düğüm ekleme sürecinden farkı yoktur. Ancak eğer denge bozulursa işte AVL Algoritması devreye girer. Dengesiz bir ağaç oluşturmanıza izin vermez. Dengeleme işlemini yapar, bu işlemden sonra insertion ya da deletion (ekleme & silme) işlemlerini gerçekleştirir.
AVL Ağacı Algoritması Adımları
Ağaçta silme ya da ekleme yapılan her düğümde;
Sol düğümün derinliği ölçülür ve bir değişkene aktarılır. x->left (düğümlerimizi x diye struct'da tuttuğumuzu varsayın)
Sağ düğümün derinliği ölçülür ve bir değişkene aktarılır. x->right
Eğer (x.left - x.right) > 1 ise
Sola Dengeler
Eğer (x.right- x.left) > 1 ise
Sağa Dengeler
Yukarıdaki 4 satırda hiçbir şey gerçekleşmese dahi, ekleme veya silme işlemlerini normal bir şekilde gerçekleştirir.
Etiketler: ağaçlar, avl ağacı, avl arama ağacı, avl balance factor, balance factor, dengeli ağaçlar
