AVL

AVL

AVL(Adelson, Velskii, Landis) ditemukan oleh G.M. Adelson-Veleskii dan E.M. Landis, dan nama AVl sendiri digunakan untuk menghargai penemu-penemunya.
AVL merupakan tree balancing pertama yang pernah ada dan merupakan salah satu yang lainnya adalah RBT.
AVL tentunya akan lebih baik untuk digunakan dibandingkan dengan RBT yang akan sangat lama untuk melakukan insert, search maupun delete nya.
AVL sangatlah mirip dengan BST tetapi bedanya AVL bisa dikatakan sebagai BST yang seimbang.


Berikut ini merupakan beberapa konsep AVL:

• Tinggi subtree : Level node terbawah dari subtree  dikurang level root subtree tsb
• Balance Factor : Tinggi subtree kanan dikurang tinggi dari subtree kiri dari suatu node
• Pada AVL, balance factor nya hanya boleh -1,0,1.
• Selebihnya dari itu, maka terjadi violation lalu harus dilakukan rotasi.
•  Tinggi sebuah sub tree kosong itu 0
•  Tinggi sebuah leaf itu 1.
• Tinggi pada tree dapat dihitung dengan cara tinggi terbesar dari children nya+1, jadi missal ada 2 anak yang satu tinggi nya 1, sedangkan yang satu lagi 2. Maka node tersebut memiliki tinggi 2+1=3.

Angka yang merah merupakan balance factor, sedangkan yang hitam merupakan tiiggi subtree.

Dan, pada node yang isi angka 17 terjadi violation karena balance factor nya 2.

Berikut ini merupakan contoh AVL:

Cara-cara rebalance AVL ada 2:

1.       Single rotation: dilakukan bila terjadi violation dimana berbentuk node kiri dengan deepest kiri(left-left) / node kanan dengan deepest node nya kanan (right-right) .

       

2.       Double rotation : dilakukan bila terjadi  violation dimana berbentuk node kiri dengan deepest node nya dikanan (left, right) / node kanan dengan deepest node nya dikiri (right-left).

Operasi-operasi pada AVL:

a.       Insert

a.       Cara insert nya sama dengan insert pada BST.

b.      Setelah data diinsert maka dilakukan trace dari data yang diinsert sampai ke root, dimana balance factor nya harus maksimal 1, jika tidak maka lakukan single rotation / double rotation tergantung situasi, jika sudah lakukan terus menerus sampai root.

b.      Delete

a.       Cara delete sama seperti delete pada BST.

b.      Lakukan trace dari node yang didelete tadi sampai root, jika terjadi violation, maka lakukan single rotation/double rotation , lalu trace lagi sampai root.