AVL Tree

AVL tree memiliki dasar binary search tree namun AVL tree membuat agar tree dapat berjalan dengan kecepatan mencari secepat O(logn). cara agar membuat binary search tree agar tetap seimbang adalah dengan menggunakan AVL tree. AVL tree bekerja dengan membandingkan tinggi dari tree bagian kiri dan kanan agar tetap seimbang dengan selisih 1 atau sama.

Gambar AVL tree 1.1,

AVL tree mempunyai dua fungsi yaitu insertion dan rotation. Insertion dalam AVL tree berbeda dengan binary search tree dimana AVL tree akan mengecek tinggi dari tree bagian kiri dan kanan. jika tinggi dari tree bagian kiri dan kanan selisih satu atau sama tingginya maka insertion akan ditambahkan tanpa memerlukan rotation. rotation adalah cara agar AVL tree dapat terjaga seimbang. ada 4 jenis rotasi dalam AVL tree yaitu single right rotation, single left rotation, left right rotation, dan right left rotation.