AVL TREE

AVL Tree adalah Binary Search Tree yang memiliki perbedaan level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree digunakan untuk menyeimbangkan BST, dengan AVL Tree waktu pencarian dan bentuk tree dipersingkat dan disederhanakan.

Berikut merupakan contoh dari AVL Tree



Angka 0 menandakan tidak memiliki perbedaan level antara subtree kiri dan subtree kanan
Angka 1 menandakan memiliki perbedaan 1 level yaitu berada pada subtree kanan (subtree kiri < subtree kanan)
Angka -1 menandakan memiliki perbedaan 1 level yaitu berada pada subtree kiri(subtree kanan < subtree kiri)

Penambahan node pada AVL tree (Insert)

Untuk menjaga BST tetap seimbang, setiap dilakukan penyisipan node, dilakukan pemeriksaan node baru. Jika tidak seimbang, maka akan dilakukan proses penyeimbangan yaitu Single Rotation dan Double Rotation.

Single Rotation

Single Rotation dilakukan bila kondisi AVL Tree waktu akan ditambahkan, searah left-left / right-right



Double Rotation

Double Rotation dilakukan bila kondisi AVL Tree berlawan arah, left-right atau right-left.

Rotasi pertama
Rotasi kedua




Penambahan node pada AVL tree (Delete)

Tidak hanya dapat melakukan insert, tetapi ada operasi lainnya bernama delete, proses delete ini dilakukan sama seperti BST yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau yang terkecil pada subtree kanan. Setelah dilakukan penghapusan, dicek kembali apakah tree sudah seimbang atau belum, jika tidak seimbang, maka akan dilakukan proses penyeimbangan dengan menggunakan single rotation atau double rotation.

Delete node 60

Pada node 55 tidak seimbang maka akan dilakukan single rotation

Pada node 50, tree menjadi tidak seimbang, maka dilakukan double rotation

Hasil akhir setelah dilakukan double rotation



Demikian penjelasan saya mengenai AVL Tree.