AVL Tree

AVL Tree adalah lanjutan dari Binary Search Tree. Dengan AVL Tree, Binary Search Tree yang tingginya berat sebelah akan dibuat menjadi rata dengan mengubah posisi dari node yang membuat tree tidak seimbang. Pengubahan posisi tersebut dilakukan dengan cara rotating, dimana node yang menjadi akar masalah dalam tree tersebut akan dipindahkan menjadi node yang berada diatas nya dan node yang berada pada atasnya akan berubah tempat mengikuti dengan aturan Binary Search Tree.

Rotating terbagi menjadi dua, yaitu Single Rotate dan Double Rotate.

Seperti namanya, Single Rotation merupakan Rotasi yang dilakukan sekali saja. Rotasi ini hanya dilakukan sekali saja, dengan menemukan node yang membuat tree tersebut tidak seimbang, lalu menggantikan node tersebut dengan node yang berada di bawahnya serta memindah node itu sendiri untuk menyeimbangkan tree tersebut.

Node 30 menempati node 25 dan node 25 menjadi leaf kiri node 30 untuk menyeimbangkan tree.

Double Rotation juga seperti namanya, merupakan rotasi yang dilakukan dua kali karena terjadinya percabangan dalam menyeimbangkan tree, seperti berikut ini.

Node 70 mengalami double rotation menempati posisi node 50, dan node yang di insert, 65, yang seharusnya menjadi leaf kiri dari 70 menjadi leaf kanan 50, dan node 50 menjadi leaf kiri node 70.

Sumber :

https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

https://www.geeksforgeeks.org/avl-tree-set-1-insertion/