AVL Tree

AVL Tree Summary

AVL tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL tree berguna untuk menyeimbangkan Binary Search Tree. Dengan AVL tree, pencarian menjadi lebih singkat. Sebuah tree dikatakan seimbang jika jumlah tingkatannya berbeda 0 atau 1. Ketika sub-tree memiliki perbedaan tingkatan 2 atau lebih disitulah dikatakan melanggar aturan AVL tree, jadi kita harus melakukan rotation.

Ada 2 cara untuk menyeimbangkan, yaitu dengan single rotation dan double rotation.

Single rotation terjadi ketika ada node yang tidak seimbang, dan harus dirotate sebanyak 1 kali. Sedangkan ketika lebih dari 1 kali disebut double rotation. 

Ada 4 rotation dalam melakukan rotation:

• LL rotation: Ketika node baru yang melanggar diinsert di sebelah kiri sub-tree.
• RR rotation: Ketika node baru yang melanggar diinsert di sebelah kanan sub-tree.
• LR rotation: Ketika node baru yang melanggar diinsert di sebelah kanan sub-tree bagian sub-tree kiri.
• RL rotation: Ketika node baru yang melanggar diinsert di sebelah kiri sub-tree di sub-tree kanan.

Ketika melakukan deletion di root, node paling besar sebelah kiri atau node paling kecil sebelah kanan akan menggantikan posisi rootnya. Lalu, dilihat lagi apakah sudah seimbang atau belum. Kalau belum, dilakukan rotation.