AVL Tree

AVL Tree adalah binary tree yang memenuhi syarat minimal height atau ketinggian dari jumlah node yang ada. AVL Tree merupakan salah satu dari Balanced Search Tree.

Balanced Search Tree digunakan agar binary tree memiliki height terkecil sehingga bisa mempertahankan complexity-nya O(log n) dimana n adalah jumlah node.

Dalam AVL Tree terdapat yang namanya balance factor yang nantinya akan digunakan untuk menentukan perlu atau tidaknya rebalancing dilakukan. Balance factor (bf) dihitung dengan mengurangkan tinggi dari anak kiri dengan tinggi dari anak kanan.

Rebalancing dilakukan ketika pada suatu node terjadi violated, dimana bf (balance factor) bernilai lebih dari 1 atau kurang dari -1. 

Dapat dilihat dari contoh diatas, dengan adanya AVL Tree maka tinggi dari sebuah tree dapat diminimalisir. Pada awalnya tinggi tree tersebut 4 lalu berubah menjadi 3 jika dijadikan AVL tree, sehingga jika melakukan pencarian pada suatu node hanya perlu maksimal 3 step yang sebelumnya maksimal 4 step.