AVL Tree

AVL Tree

AVL Tree adalah height balancing binary search tree. AVL Tree mengecek perbedaan dari height sub-tree kiri dan kanan tidak melebihi dari 1. Perbedaan ini disebut dengan Balance Factor.

Dapat dilihat dari gambar di atas, tree yang pertama balanced dan dua tree disebelahnya tidak balanced. Di tree kedua, subtree kiri dari C memiliki height 2, sementara subtree kanannya memiliki height 0, jadi perbedaannya adalah 2. Sama seperti pada tree ketiga, subtree kiri dari A memiliki height 0 dan subtree kanannya memiliki height 2, sehingga perbedaan heightnya adalah 2. Dalam AVL Tree, perbedaan height yang diperbolehkan tidak melebihi dari 1.

Apabila perbedaan dari heightnya melebihi dari 1, maka treenya akan dibalance menggunakan rotation. Ada 4 cara AVL Tree menggunakan rotation:

1. Left rotation (Single rotation)
2. Right rotation (Single rotation)
3. Left-Right rotation (Double rotation)
4. Right-Left rotation (Double rotation)

Single Rotation

Apabila sebuah node dimasukkan ke subtree kanan dari subtree B, maka akan dilakukan left rotation.

Apabila sebuah node dimasukkan ke subtree kiri dari subtree C, maka akan dilakukan right rotation.

Double Rotation

Proses dari left-right rotation,

Sebuah node B telah diinsert ke subtree kanan dari subtree kiri A. Hal ini membuat C menjadi unbalanced node.

Pertama, kita melakukan left rotation pada subtree kiri dari C. Hal ini membuat A menjadi subtree kiri dari B.

Node C masih unbalanced, tetapi sekarang disebabkan oleh subtree kiri dari subtree kiri B.

Sekarang kita akan melakukan right rotation, membuat B menjadi root node baru dari subtree ini. C sekarang menjadi subtree kanan dari subtree kirinya sendiri.

Sekarang treenya balanced.

Proses untuk right-left rotation sama, dengan proses awalnya dimulai dengan right rotation kemudian dilanjutkan dengan left rotation.

Insertion & Deletion

Untuk proses insertion & deletion pada AVL Tree, tinggal input saja node yang dimasukkan, kemudian AVL Tree akan mengecek apakah tree tersebut balance atau tidak, apabila unbalanced maka akan dilakukan single rotation atau double rotation. 

Sama juga halnya dengan deletion, tinggal input node yang ingin dihapuskan, kemudian AVL Tree akan mengecek apakah tree tersebut balance atau tidak, apabila unbalanced maka akan dilakukan single rotation atau double rotation.

Referensi

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