AVL Tree

Pada pertemuan kali ini saya mempelejari tentang AVL Tree. AVL Tree merupakan salah satu contoh dari balanced binary search tree.

AVL Tree harus memiliki sisi yang jarangnya satu sama lain tidak boleh lebih dari 1. Jika lebih maka itu tidak balance dan harus segera diperbaiki. Dan lebih baik apabila tidak ada perbedaan sama sekali agar menjadi benar-benar balance.

Setiap AVL Tree melakukan insert maupun delete harus diperhatikan balance atau tidak.

Jika AVL Tree tersebut tidak balance maka akan ada 2 pilihan cara membenarkannya: yaitu, single rotation dan double rotation.

Sisanya secara dasar sama dengan tree biasa. Jika lebih besar dari parent akan dimasukkan ke sisi kanan dan jika lebih kecil akan dimasukkan ke sisi kiri.

Ketika melakukan insertion dapat terjadi 4 kasus dimana masing-masing tidak seimbang dan harus diperbaiki.

1. LL rotation, hal ini dapat diperbaiki dengan single rotation dengan mudahnya.
2.  RR rotation, sama pula halnya seperti LL rotation hal ini dapat diperbaiki dengan single rotation
3. LR rotation, sedangkan dengan ini tidak bisa dengan single rotation tapi harus dengan double rotation.
4. RL rotation, sama halnya dengan LR rotation hal ini dapat dipeerbaiki dengan double rotation.