Monday, May 4, 2020

AVL Tree

AVL Tree
AVL Tree merupakan tipe binary tree yang dapat menyeimbangkan / self-balancing dirinya sendiri dimana perbedaan tinggi / height dari subtrees kiri dan kanan tidak boleh lebih dari satu untuk semua nodes. Kegunaan dari AVL Tree adalah mempercepat dan membuat operasi BST lebih efisien.
Contoh A
Gambar tree Contoh A diatas merupakan AVL Tree karena perbedaan tingginya hanya 1.
Contoh B
Gambar tree Contoh B dibawah bukanlah merupakan AVL Tree karena perbedaan tingginya lebih dari satu.

AVL Tree Insertion [Rotations]
Rotasi / Rotations AVL Tree dapat dibagi menjadi dua jenis yakni,
a. Single Rotation
    Single Rotation dapat dibagi menjadi dua jenis yakni,
        Single Left Rotation [LL Rotation]
        Single Right Rotation [RR Rotation]

b. Double Rotation
    Double Rotation dapat dibagi menjadi dua jenis yakni,
        Left Right Rotation [LR Rotation]
        Right Left Rotation [RL Rotation]
Penjelasan
Single Rotation
Jika treenya menjadi unbalanced, saat sebuah node di insert ke kanan subtree dari subtree kanan maka kita melakukan single left rotation.
Left Rotation
LL Rotation
Sebaliknya jika kondisinya di kiri, maka kita melakukan single right rotation.
Right Rotation
RR Rotation

Double Rotation
Left Right rotation adalah kombinasi dari left rotation lalu diikuti dengan right rotation, agar lebih dapat dipahami dapat dilihat dari gambar di bawah.
Right Rotation
Sebuah node telah diinsert ke subtree kanan dari subtree kiri,
hal ini membuat tree menjadi tidak balance.

Left Rotation
Pertama, kita melakukan left rotation di subtree kiri C,
hal ini membuat A menjadi subtree kiri dari B.

Right Rotation
Lalu kita melakukan right rotation kepada treenya,
hal ini membuat B menjadi root baru dari tree dan C menjadi subtree kanan dari B.

Balanced Avl Tree
Untuk Right Left Rotation dilakukan jika kondisinya kebalikannya.
Left Subtree of Right Subtree    Subtree Right Rotation    Left Rotation    Balanced AVL Tree
    
Deletion
Deletion pada AVL Tree sama dengan Deletion pada BST, tetapi Deletion pada AVL Tree dapat menyebabkan ketidakseimbangan / unbalance pada tree. Untuk membuat AVL Tree tetap AVL Tree setelah deletion maka diperlukannya penyeimbangan ulang / re-balancing pada tree.

References:
https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm
https://www.geeksforgeeks.org/avl-tree-set-1-insertion/
https://www.geeksforgeeks.org/avl-tree-set-2-deletion/
https://binusmaya.binus.ac.id/newStudent/#/class/resources.COMP6048/010544/1920/LEC/12104

No comments:

Post a Comment