Adelson-Velsky and Landis (AVL) Tree

Adelson-Velsky and Landis (AVL) tree adalah sebuah struktur data berupa tree yang mampu melakukan self-balancing. Self-balancing adalah kemampuan untuk memperkecil perbedaan ketinggian antara satu node dengan node lainnya dari tree secara otomatis. AVL tree memiliki kaidah ciri khas sebagai berikut:

• Merupakan tree dengan jenis Binary Search Tree.
• Untuk setiap node, perbedaan ketinggian antara node kiri dari subtree dan node kanan dari subtree adalah sebesar 1 (satu).

Operasi
Seluruh operasi self-balancing pada AVL tree dilakukan setelah operasi Binary Search Tree. Operasi dasar Binary Search Tree dapat dilihat di link ini. Operasi Binary Search Tree dapat menyebabkan perubahan struktur tree sehingga menyebabkan terjadinya pelanggaran kaidah AVL tree. Tree yang melanggar tersebut dimodifikasi agar dapat kembali memenuhi kaidah ciri khas AVL tree.

Pelanggaran Kaidah AVL
Terdapat empat jenis pelanggaran dari kaidah AVL tree:

1. Insersi ke subtree kiri dari subtree kiri
2. Insersi ke subtree kanan dari subtree kiri
3. Insersi ke subtree kiri dari subtree kanan
4. Insersi ke subtree kanan dari subtree kanan

Kasus pelanggaran nomor 1 dan 4 adalah simetris dan hanya membutuhkan rotasi sekali, sedangkan pelanggaran nomor 2 dan 3 juga simetris namun membutuhkan rotasi dua kali.

Solusi Left-Left Rotation (LLR) untuk Kasus Pelanggaran Nomor 1

Pada kasus ini, insersi node 7 menyebabkan node 9 menjadi tidak balanced. Solusinya, dilakukan sekali rotasi LLR pada node 9 sehingga perbedaan ketinggian antar node kembali menjadi satu.

Solusi Right-Right Rotation (RRR) untuk Kasus Pelanggaran Nomor 4

Pada kasus ini, insersi node 29 menyebabkan node 15 menjadi tidak balanced. Solusinya, dilakukan sekali rotasi RRR pada node 15 sehingga perbedaan ketinggian antar node kembali menjadi satu. Rotasi RRR kurang lebih mirip dengan rotasi LLR.

Solusi Left-Right Rotation (LRR) untuk Kasus Pelanggaran Nomor 2

Untuk kasus pelanggaran nomor 2, rotasi sekali saja tidak akan cukup untuk mengembalikan balance.

Sebagai contoh, pada kasus ini, setelah dilakukan insersi node 7, rotasi dilakukan dengan melakukan rotasi RRR sekali pada node 5, kemudian rotasi LLR pada node 8.

Solusi Right-Left Rotation (RLR) untuk Kasus Pelanggaran Nomor 3

Demikian juga untuk kasus pelanggaran nomor 3, rotasi sekali saja tidak akan cukup untuk mengembalikan balance. Rotasi untuk menyelesaikan kasus ini mirip dengan rotasi kasus sebelumnya, yaitu setelah dilakukan insersi node 5, rotasi dilakukan dengan melakukan rotasi LLR sekali pada node 7, kemudian rotasi RRR pada node 4.

Referensi
Cormen, T. and Leiserson, C. (2014). Introduction to algorithms. 3rd ed.
Karumanchi, N. (2016). DATA STRUCTURES AND ALGORITHMS MADE EASY. Careermonk Publications.