AVL tree

AVL tree adalah pengembangan dari binary tree yang nantinya tree akan dapat self balancing.

Penamaan AVL tree diambil dari penemunya yang adalah Georgy Adelson-Velsky dan Landis.


Tree dinyatakan balance jika ketinggian anak kiri dan kanan sama atau setidaknya berselisih 1.


Self balancing dari AVL tree sendiri pada dasarnya dilakukan dengan rotasi. Rotasi yang digunakan tergantung dari posisi node mana yang tidak balance dan lurus atau tidaknya node yang tidak balance dilihat dari root..

Ada 2 jenis rotasi untuk menyeimbangkan tree yaitu, Single Rotate dan Double Rotate.

Single Rotate digunakan jika untuk ke node yang tidak balance dari root adalah lurus.

Double Rotate digunakan jika untuk ke node yang tidak balance dari root adalah tidak lurus

First rotation

Second rotation

Source : PPT