AVL Tree

AVL tree adalah Binary Search Tree/BST yang mempunyai sifat self-balancing . AVL Tree ditemukan oleh  Adelson-Velsky dan Landis dan tree ini dinamakan AVL/inisial nama penemunya. AVL tree melakukan penyeimbangan sendiri dengan faktor dimana setiap node mempunyai perbedaan Tinggi atau level maksimal 1 dengan  jumlah anaknya.

Contoh AVL Tree:

Tree ini diklasifikasikan AVL Tree karena setiap node mempunyai perbedaan bernilai 1 Bandingkan rute 1->10->11 dengan tingkat 2 sama rute 1->0 dengan tingkat 1. Jika diselisihkan node 1 adalah puncak node yang mempunyai perbedaan nilai 1

Insertion AVL Tree

Sifatnya AVL Tree adalah setiap node harus mempunyai perbedaan tingkat nilai 1. Jika ditambahkan atau dikurangkan node maka Tree akan tidak dibilangkan berjenis AVL jika tingkatnya lebih dari nilai 1. Untuk membenarkan tree tersebut dilakukannlah rotasi. Ada 2 macam rotasi yaitu Single dan Double Rotation

Rotasi ini tergantung pada bagian tree yang ditambahkan. Jika ada satu bagian dimana node puncaknya menjadi tidak stabil atau tidak bernilai 1 maka node yang mempunyai tidak nilai seimbang tersebut akan menjadi poros rotasi untuk menyesuaikan tree yang barunya.

Tree ini sama seperti tree yang diatas sebelumnya. Tapi ditambahkan Node 20 dia bagian kanannya. Sekarang jika dihitung perbedaan tinggi rute 1->0 dengan 1 tingkat, dengan rute 1->10->11->20 dengan tingkat 3 maka dinyatakan tidak seimbang dan tidak menjadi AVL Tree.

Untuk menyelesaikan masalah ini dilakukannya rotasi. Dalam kasus ini dilakukannya Single Rotation ke kiri

Dan ini hasilnya. Node 10 dijadikan puncak tree dan seluruh tree dikatrol atau digeser ke kiri. Tapi Node 10 sudah mempunyai anak 10 dan 11 di tree sebelumnya, jadi mengapa node 9 menjadi anaknya node 1?

Ini dikarenakan peraturan BST dimana node sebelumnya disesuaikan. Node 1 ditarik ke kiri dengan anaknnya 0 dan 10 menjadi puncak barunya. Node 9 akan mengikuti node yang kurang dari 10 tapi lebih dari 1 sehingga menjadi anak Node 1.

Gambar diatas merupakan proses penyeimbangan tree dengan Double Rotation. Beda dengan Single Rotation, rotasi ini melibat melakukan 2 kali rotasi. Biasa rotasi ini dilakukan bila ketidak seimbangannya bersifat lekuk atau kiri-kanan. Tree diatas dilakukan rotasi kiri sekal dengan node 5 sebagai porosnya. Tapi setelah rotasi pertama tree masih tidak seimbang maka  dilakukanlah rotasi kedua ke kanan  dengan 10 sebagai porosnya. Dan hasil akhirnya menjadi seimbang.

Deletion AVL Tree

Untuk membahas Deletion kita akan menggunakan AVL tree berikut:

Tree ini sudah mempunyai semua node seimbang dengan nilai 1. Tapi jika misalnya node 7 dihilangkan maka node 5 akan mengambil posisi 7

Tapi Jika dilihat Hasilnya, Tree ini menjadi tidak seimbang. Untuk menyelesaikan masalah ini kita lakukan single rotation ke kiri dengan Node 5 sebagai poros.

 

Sehingga menjadi begini. Node 10 dinaikan dan node 5 menjadi anaknya 10 dan node 9 menjadi anaknya 5.