AVL Tree adalah Binary Search Tree yang memiliki perbedaan level maksimal 1 antara subtree kiri dan subtree kanan dan dilakukan penyeimbangan. Balance Factor dapat dicari dengan mencari selisih antara subtree kiri dan subtree kanan. AVL Tree digunakan untuk menyeimbangkan Binary Search Tree dan mempersingkat pencarian serta bentuk tree dapat disederhanakan.
Dalam membuat AVL Tree, terdapat 2 proses penyeimbangan, yaitu
1. Single Rotation
Single Rotation dilakukan bila kondisi AVL Tree searah, left - left atau right - right.
2. Double Rotation
Double Rotation dilakukan bila kondisi AVL Tree tidak searah, left - right atau right - left.
Rotation Pertama Rotation Kedua
Sama seperti BST, operasi pada AVL Tree ada 2, yaitu :
a. Insertion
Sama seperti BST, node baru akan dicek terlebih dahulu apakah lebih besar atau lebih kecil dari node sebelumnya dan node baru akan diletakkan sebagai leaf. Setelah selesai di-insert, maka AVL Tree akan melakukan penyeimbangan kembali baik menggunakan Single Rotation ataupun Double Rotation tergantung arahnya (left - left , left - right, right - right, right - left).
b. Deletion
Proses delete node di AVL Tree juga hampir sama dengan BST. Node yang akan dihapus akan dicari terlebih dahulu. Jika node yang akan dihapus tidak memiliki anak atau leaf, maka dapat langsung dihapus. Jika node yang akan dihapus memiliki anak atau leaf, maka node yang dihapus akan digantikan oleh node terbesar dari subtree kiri atau node terkecil dari subtree kanan. Setelah dilakukan delete, maka selanjutnya akan dilakukan proses penyeimbangan dengan Single Rotation ataupun Double Rotation seperti yang dilakukan pada Insertion.
Sumber :
PPT BINUSMAYA
Bagus dan terima kasih