AVL TREE

AVL Tree adalah self-balancing tree dari BST(Binary Search Tree) dimana kedalaman dari sisi kiri dan sisi kanan harus sama dan maksimal beda 1. Mengapa menggunakan AVL Tree? Karena AVL mempertahankan kecepatan operasinya hampir O(log n) sehingga kecepatannya lebih cepat dibanding dengan BST biasa.

Agar sistem dari AVL tidak merusak BST, maka proses insertion dari AVL akan sama dengan BST namun dalam tiap prosesnya akan terjadi re-balancing jika tree yang ada tidak seimbang.

Proses Insertion :

1. Masukkan angka sama seperti insertion di BST
2. Cek apakah tree tersebut seimbang
3. JIka seimbang(maksimal beda 1 kedalaman) maka proses insertion dilanjutkan, jika tidak maka akan dilakukan rotasi agar tree tersebut seimbang.

Proses Deletion :

1. Delete angka sama seperti Deletion di BST
2. Cek apakah tree tersebut seimbang
3. JIka seimbang(maksimal beda 1 kedalaman) maka proses deletion dilanjutkan, jika tidak maka akan dilakukan rotasi agar tree tersebut seimbang.
4. Proses re-balance akan tetap berlanjut sampai semua tree seimbang(re-balance sampai ke root)

Ada 2 jenis rotasi yaitu Single Rotation dan Double Rotation:

• Single Rotation : Single Rotation digunakan saat jika node yang menyebabkan tree tidak seimbang berada pada posisi left-left atau right-right pada subtree(lurus) 

• Double Rotation : Double Rotation digunakan saat jika node yang menyebabkan tree tidak seimbang berada pada posisi left-right atau right-left pada subtree(bengkok)