AVL Tree

AVL Tree adalah versi binary tree yang memiliki perbandingan tinggi/level yang maksimal 1 antara subtree kiri dan subtree kanan. Tujuan dari AVL Tree adalah menyeimbangkan binary search tree. Dengan AVL Tree ini, waktu pencarian data dalam bentuk tree ini semakin singkat dibandingkan dengan binary search tree biasa. Untuk menjaga tree tetap seimbang, akan dilakukan pengecekan setiap kali menginsert data. Proses penyeimbangan ini ada dua jenis, yaitu single rotation dan double rotation.

1. Single Rotation

Single rotation terjadi ketika tree seperti contoh diatas tidak seimbang. Sesuai gambar diatas, angka 3 mengalami ketidakseimbangan. Kedalaman di sisi kanan 3 adalah 2 sedangkan kedalaman di sisi kiri 3 adalah 0 dan menyebabkan selisih tingginya adalah 2. Oleh karena itu, anak dari 3 yaitu 4 dinaikkan dan 3 diturunkan ke sisi kiri 4 sehingga tree tersebut seimbang. Dikarenakan hanya putar sekali, maka disebut juga dengan single rotation.


2. Double Rotation

Double rotation terjadi ketika tree seperti diatas ini tidak seimbang dan tidak dapat diselesaikan hanya dengan single rotation. Sesuai dengan gambar diatas, angka yang tidak seimbang adalah angka 6. Di sisi kanan 6, kedalamannya adalah 3 dan di sisi kirinya adalah 1, maka selisih kedalamanya adalah 2. Cara kerja double rotation yaitu melakukan rotasi pertama di angka 15 terlebih dahulu kemudian baru dilakukan rotasi kedua di angka 6. Karena terjadi 2 kali, maka disebut sebagai double rotation