AVL Tree

Pengertian AVL Tree :
AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

Contoh AVL Tree

Tree diatas adalah AVL karena perbedaan tinggi kanan dan kiri subtrees untuk setiap nodes sama dengan satu atau dibawah satu. 

Contoh bukan AVL Tree

Tree diatas bukan AVL karena perbedaan tinggi kanan dan kiri subtrees untuk 11 dan 30 diatas satu.

Mengapa AVL Tree?
Sebagian besar operasi Binary Search Tree (search,insertion,deletion,dll) membutuhkan O(h) waktu dimana h adalah ketinggian BST, bahkan bisa O(n) untuk Binary Tree yang miring. Jika ketinggian pohon disesuaikan menjadi O(log n) setelah semua operasi insertion dan deletion, maka bisa dipastikan batas atas O(Log n) untuk semua operasi. Ketinggian AVL Tree selalu O(Log n) dimana n adalah jumlah node di pohom.

Insertion
Untuk memastikan Tree tetap AVL Tree setelah semua insertion, kita harus menggunakan operasi insertion standar BST untuk penyeimbangan. Berikut adalah 4 operasi dasar yang bisa dilakukan untuk menyeimbangkan Tree tanpa melanggar properti Tree (keys(left) < key(root) < keys(right))

Single Rotation
1. Left-left rotation
Jika Tree tidak seimbang, ketika sebuah node di insert ke subtree kanan nya subtree kanan, maka kita lakukan Single Left Rotation.

Di contoh, node A menjadi tidak seimbang karena sebuah node di insert ke subtree kanan nya subtree kanan A. Rotation dilakukan dengan membuat A subtree kiri dari B.

2. Right-right rotation
AVL Tree akan menjadi tidak seimbang apabila sebuah node di insert ke subtree kiri nya subtree kiri. Tree akan membutuhkan Single right rotation.

Seperti digambar, node yang tidak seimbang akan menjadi anak kanan dari anak kiri dengan melakukan Single right rotation.

Double Rotation
3. Left-right rotation
Double rotation agak sedikit lebih kompleks dibandingkan single rotation. Agar lebih mengerti, kita harus membahas setiap langkah satu persatu. Left-right rotation adalah kombinasi left rotation diikuti right rotation.

Sebuah node di insert ke subtree kanan nya subtree kiri. Itu menyebabkan C menjadi node tidak seimbang. Skenario ini membuat AVL melakukan Left-right rotation.

Pertama kita lakukan left rotation di subtree kiri dari C. Ini membuat A menjadi subtree kiri dari B. 

Node C masih belum seimbang, tetapi sekarang karena subtree kiri dari subtree kiri.

Sekarang kita lakukan right rotation ke Tree, membuat B menjadi root baru di subtree ini. C sekarang menjadi subtree kanan dari subtree kirinya.

    

Tree sudah seimbang.

4. Right-left rotation
Double rotation kedua, adalah kombinasi dari right rotation dilanjutkan dengan left rotation.

Sebuah node telah di insert ke subtree kiri dari subtree kanan. Ini menyebabkan A menjadi tidak seimbang. 

Pertama kita lakukan right rotation di node C, membuat C menjadi subtree kanan dari subtree kiri nya sendiri (B). Sekarang B menjadi subtree kanan nya A. 

Node A masih belum seimbang karena subtree kanan dari subtree kanan, sehingga membutuhkan left rotation.

Left rotation dilakukan dengan membuat B menjadi root node yang baru dari subtree. A menjadi subtree kiri dari subtree kanan B.

Tree sudah seimbang.

Deletion
Menghapus sebuah node di AVL Tree mirip dengan BST. Deletion bisa mengganggu keseimbangan AVL Tree, maka Tree harus diseimbangkan setelahnya dengan melakukan rotation. 

Terdapat 2 kasus yang biasanya terjadi saat operasi delete dilakukan, yaitu :

- Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.
- Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Tree dengan AVL.

Rotation yang digunakan sama dengan insertion, yaitu :
1. Left Rotation
2. Right Rotation
3. Left-right Rotation
4. Right-left Rotation

Contoh Deletion:

Kita mau delete node 30 di tree diatas

Disini, node B mempunyai faktor keseimbangan 0, maka Tree di rotate dengan right rotation. Node B menjadi root, sedangkan A dipindahkan ke kanan. Anak kanan dari node B menjadi anak kiri node A.

~ Thankyou ~