AVL Tree - Self Balancing Bir Binary Tree'dir

Giriş

Kısaca 

1. AVL Tree bir Binary Search Tree'dir

2. Self Balancing Search Tree olduğu için bir işlemden sonra herhangi bir düğümün sol veya sağ tarafının alt derinliği 1'den fazlaysa kendisini tekrar dengeler.

3. AVL Tree aynı Red-Black Tree gibi sadece bellekte saklanır

Açıklaması şöyle

In an AVL tree, for every node v, the difference between the height of v's right sub-tree and the height of v's left sub-tree must be at most 1.

1. Binary Tree Özelliği

AVL ağacı ikilik ağaç olduğu için yapısı şöyledir.

struct node {
  struct node *left; 
  struct node *right 
  ...
}  

2. Self Balancing Özelliği

Bir düğümün sol tarafının derinliği ile sağ tarafının derinliğinin farkı en fazla 1 olan ağaçtır. Kısaca her zaman dengeli olan ağaçtır. 

Örnek

Elimizde en son ekleme işlemi ile dengesiz hale gelene bir ağaç olsun.

  4
/   \
1    11
    /
   7
 /  \
5    9

AVL algoritması bu ağacı dengeli hale getirir. Şöyle yaparız.

    11
   /   \
  4    7
 /    / \
1    5   9