AVL Tree Summary

AVL TREE

AVL Tree merupakan Binary Search Tree (BST) yang seimbang sehingga lebih cepat untuk mencarinya dibanding dengan BST. Didalam AVL keseimbangan haruslah sangat diperhatikan tiap node tidak boleh kurang dari -1 dan tidak boleh juga lebih dari 1. Cara menentukan apabila balance atau tidak adalah dengan jumlah bagian terpanjang sebelah kanan - bagian terpanjang sebelah kiri.

Berikut adalah Contoh AVL Tree:

Diatas adalah contoh AVL Tree yang sempurna karena perbedaan antara yang kanan dengan yang sebelah kiri adalah 0.

Di AVL Tree setiap setelah melakukan Insertion atau deletion harus di cek kembali keseimbangan di dalam AVL Tree-nya, Apabila AVL Tree belum seimbang maka ada dua kemungkinan cara untuk menyeimbangkan Tree tersebut.

Yang pertama adalah dengan menggunakan Single Rotation

Dibawah ini adalah contoh AVL Tree yang tidak seimbang:

Karena yang bagian sebelah kiri – bagian sebelah kanan adalah 2 maka AVL Tree diatas belum lah seimbang dan AVL Tree diatas dapat diseimbangkan dengan menggunakan Single Rotaion sehingga hasilnya menjadi :

Di AV L Tree yang salah diatas setelah angka 50 dari bagian sebelah kiri dengan bagian sebalah kanan perbedaannya adalah 2 sehingga jika diselesaikan menggunakan single rotation angka 28 di tarik kekanan dan angka 50 nya juga ditarik kekanan agar seimbang. Untuk anak sebelah kanan dari angka 28 tadi akan di insert ulang dari atas sehingga menjadi anak sebelah kiri angka 50.  

Untuk Single rotation kiri dan kanan (LL & RR) itu caranya sama seperti yang diatas perbedaannya adalah dalam LL Single Rotation setiap node atau angka bergerak satu posisi ke sebelah kiri dari posisi saat ini dan kalau RR Single Rotation setiap node atau angka bergerak satu posisi ke kanan dari posisi saat ini.

Cara yang kedua adalah dengan menggunakan Double Rotation

Diatas merupakan AVL Tree yang belum seimbang karena diangka 55 di bagian anak sebalah kanannya jika dikurang dengan anak disebelah kirinya merupakan 2 sehingga perlu diseimbangkan dengan menggunakan Double Rotation seperti berikut:

Langkah pertamanya adalah dengan menarik angka 58 sehingga anak dari angka 58 ketika di insert menjadi anak sebelah kiri dari angka 60, langkah yang keduanya adalah menarik lagi angka 58 sehingga angka 55 menjadi anak sebelah kiri dari angka 58 (cara mudah untuk menentukan letak anaknya adlaah dengan insert dari pusat teratas).

Dalam double rotation juga dapat dilakukan melalui Left Double rotation dan Right Double Rotation seperti namanya rebalancingnya dilakukan melalui sebelah kiri dan sebelah kanan.