Apa sih AVL Tree itu? AVL Tree merupakan subtipe dari Binary Search Tree (BST). AVL Tree diberi nama sesuai dengan nama penemunya, yaitu Adelson, Velskii, dan Landis. Lalu, apa bedanya dengan BST? Jadi, bedanya antara BST dan AVL Tree adalah AVL Tree memiliki kemampuan untuk menyeimbangkan secara dinamis sebuah BST agar tetap memiliki kompleksitas log (n). Mengapa demikian? BST memiliki kelemahan, kelemahan tersebut akan membuat kompleksitas pencarian suatu data dalam BST menjadi O(n). Contohnya kita akan menginputkan 5 bilangan angka berurutan dari angka 1. Maka yang terjadi adalah 2 menjadi anak kanan dari 1, 3 menjadi anak kanan dari 2, 4 menjadi anak kanan dari 3, dan 5 menjadi anak kanan dari 4. Jika kita akan mencari data bernilai 4. Maka program harus melakukan 4 kali looping. Hal inilah yang membuat kompleksitas dari BST tidak konsisten. Ketika input telah dimasukkan ke dalam tree, AVL Tree akan mengecek tinggi atau kedalaman dari anak kiri dan anak kanan. Apabila perbedaan tinggi tersebut lebih dari 1, maka akan dilakukan penyeimbangan. Berikut merupakan contoh dari tree yang seimbang dan tidak seimbang:
Pada tree ke-2, anak kiri dari C memiliki ketinggian 2 dan anak kanan dari C memiliki ketinggian 0 (tidak ada). Pada tree ke-3, anak kanan dari A memiliki ketinggian 2 dan anak kiri memiliki ketinggian 0. Karena perbedaan ketinggian pada tree ke-2 dan ke-3 adalah 2, maka akan dilakukan penyeimbangan.
Penyeimbangan
Penyeimbangan tree dapat dilakukan dengan metode rotasi. Dalam AVL Tree ada 2 cara rotasi, yaitu single rotation dan double rotation. Berikut merupakan contoh dari single rotaion:
Ketika node 12 dimasukkan, maka tree akan menjadi tidak seimbang. Mengapa tidak seimbang? Karena anak kiri dari node 30, memilki ketinggian 4 dan anak kanannya memiliki ketiggian 2. Perbedaan ketiggian tersebut lebih dari 1, maka akan dilakukan penyeimbangan.
Karena yang memiliki ketinggian lebih banyak adalah anak kiri dari node 30 dan dari node 22 yang miliki ketinggian lebih banyak adalah anak kiri juga, maka node 22 akan naik, node 30 menjadi anak kanan dari node 22, dan node 27 lepas dan menjadi anakkiri dari node 30.
Lalu, kapan double rotation akan digunakan? Doube Rotation akan digunakan apabila dalam kasus diatas, dari node 22 yang memiliki ketingan lebih banyak adalah anak kanan. Misalnya, node 12 kita ganti degan node 28 lalu kita tambahkan node 25. Maka perbedaan ketinggian anak kiri dan anak kanan dari node 30 akan menjadi 2. Oleh karena itu, node 27 akan naik dan node 22 menjadi anak kiri dari node 27. Lalu setelah itu, node 27 akan naik menggantikan posisi node 30 dan node 30 akan menjadi anak kanan dari node 27.
References
Tidak ada komentar:
Posting Komentar