Apa Itu AVL Tree?

AVL Tree adalah salah satu bentuk self-balancing tree dari sebuah binary search tree. AVL Tree dikatakan balance (seimbang) apabila nilai absolut dari balance factor dalam masing-masing node tidak melebihi satu. Apabila nilai tersebut lebih dari satu, maka node tersebut akan dinyatakan sebagai tidak seimbang. Karena terdapat sebuah node yang tidak seimbang maka node tersebut telah melakukan pelanggaran sifat self-balancing tree dari sebuah AVL Tree, maka perlu dilakukan perbaikan pada tree tersebut. 

Balance factor sebuah node dapat dihitung dengan mengurangi nilai height subtree anak kiri dengan nilai height subtree anak kanan dari node tersebut, sedangkan height sendiri adalah jumlah edge yang ada dari root menuju leaf node paling bawah (level tertinggi).

Contoh tidak balance

Contoh balance

Untuk memperbaiki tree yang melanggar sifat self-balancing tree, maka dilakukanlah rotation. Ketika melakukan rotation pada node X, Y, dan Z, node Y sebagai titik putar dikatakan sebagai pivot node, sehingga putaran bertumpu pada pivot node tersebut. Untuk kasus yang tidak berat sebelah (balance factor node yang tidak balance berbeda tanda dengan balance factor anak node). Maka dilakukan double rotations.

Referensi

https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.html