Laporan Materi Pembelajaran Data Structure : AVL Tree

Di post ini, saya akan membahas materi Data Structure yang membahas tentang AVL tree, selamat membaca!


AVL Tree

AVL tree adalah self-balancing binary search tree di mana setiap node mempertahankan informasi tambahan yang disebut balance factor yang nilainya -1, 0 atau +1. Nama AVL tree dibuat berdasarkan nama penemunya yakni Georgy Adelson-Velsky dan Landis.


Balance Factor

Balance factor dari sebuah node dalam AVL tree adalah perbedaan antara ketinggian subtree kiri dan subtree kanan node tersebut. Balance factor bisa dihitung dengan mengurangkan krtinggian subtree kiri dengan subtree kanan atau sebaliknya. Nilai dari balance factor harus selalu -1, 0, atau 1, jika sebuah tree tidak memenuhi persyaratan tersebut, maka tree tersebut bukan AVL tree.

Contoh dari AVL tree yang benar
Contoh dari AVL tree yang salah





Insertion

Seperti RBT, insertion agak rumit dan melibatkan sejumlah kasus pada AVL tree. Implementasi insertion AVL tree banyak bergantung pada penambahan atribut tambahan, balance factor ke setiap node. Faktor ini menunjukkan apakah tree itu berat-kiri (ketinggian subtree kiri 1 lebih besar dari pada subtree kanan), seimbang (kedua subtree itu sama tinggi) atau berat-kanan (tinggi subtree kanan adalah 1 lebih besar dari subtree kiri). Jika keseimbangan akan dihancurkan dengan insertion, rotation akan dilakukan untuk memperbaiki keseimbangan.


Deletion

Deletion juga bisa dilakukan dengan cara yang sama seperti yang dilakukan di binary search tree. Deletion juga dapat mengganggu keseimbangan tree karena itu, berbagai jenis rotation bisa digunakan untuk menyeimbangkan tree.


Mengapa pakai AVL Tree?

AVL tree mengontrol ketinggian binary search tree dengan tidak membiarkannya miring/berat sebelah. Waktu yang diambil untuk semua operasi di binary search tree dengan tinggi h adalah O (h). Namun, dapat diperpanjang ke O (n) jika BST menjadi miring. Dengan membatasi ketinggian ini untuk log n, AVL tree memaksakan batas atas pada setiap operasi menjadi O (log n) di mana n adalah jumlah node.


Demikian penjelasan saya mengenai AVL tree.


Referensi: 


Comments

Post a Comment