AVL Tree

AVL Tree merupakan pengembangan dari Binary Search Tree. AVL Tree memberikan kompleksitas yang lebih rendah, khususnya dalam worst case, karena AVL Tree menyeimbangkan root-root dari Binary Search Tree. Dalam melakukan insertion, deletion dan searching, kompleksitasnya sangat dipengaruhi oleh tinggi dari pohon tersebut. Apabila Binary Search Tree memiliki cabang yang cenderung timpang, misal kebanyakan data berada di sisi kiri sementara sisi kanan kosong, itu berpengaruh terhadap kompleksitasnya sendiri. Dan AVL Tree menyelesaikan masalah ini dengan menyeimbangkan cabang-cabangnya sehingga tidak terlalu timpang. Ini yang disebut dengan Balanced Binary Search Tree dan AVL Tree ini merupakan salah satu dari bentuk Balanced Binary Search Tree.

Tinggi sebuah node:

- Tinggi dari sebuah subtree kosong adalah 0

- Tinggi leaf adalah 1

Balance Factor: Perbedaan tinggi antara subtree kiri dan subtree kanan dari sebuah node

*Balance factor sebuah node hanya boleh paling besar 1

Jadi, ketika sebuah node memiliki balance factor lebih dari 1, maka node tersebut dinyatakan melanggar aturan AVL Tree (Violated).

Untuk insertion dan deletion sama aturannya seperti Binary Search Tree, namun untuk AVL Tree ini setelah insert ataupun delete, kita harus memastikan tree dalam kondisi seimbang, jika tidak maka kita harus "Rebalance".

Ada 4 kasus dalam rebalance sebuah Tree:

1. Node paling bawah (dalam insertion merupakan node yang diinsert) berada di bagian kiri dari sub tree kiri node yang dinyatakan violated.

2.  Node paling bawah (dalam insertion merupakan node yang diinsert) berada di bagian kanan dari sub tree kanan node yang dinyatakan violated.

3.  Node paling bawah (dalam insertion merupakan node yang diinsert) berada di bagian kiri dari sub tree kanan node yang dinyatakan violated.

4.  Node paling bawah (dalam insertion merupakan node yang diinsert) berada di bagian kanan dari sub tree kiri node yang dinyatakan violated.

Untuk kasus 1 dan 2 menggunakan single rotation, untuk kasus 3 dan 4 menggunakan double rotation (Dua kali single rotation).

Insertion

Cek parent dari node yang sudah dicek, mulai dari node yang diinsert. Perhatikan balance factornya, jika ada yang menyalahi aturan, maka rebalance.

Single Rotation

Double Rotation

Deletion

Sama seperti insertion, cek satu per satu dari node yang dihapus sampai ke root, kalau ada yang menyalahi aturan balance factor, maka rebalance.

Single Rotation

Double Rotation