AVL Tree

Jadi pada pertemuan tanggal 28 April 2020, kelas kami membahas tentang AVL Tree. Penamaan AVL Tree berasal dari 2 penemu nya yang bernama "Adelson-Veleskii dan Landis". Fungsi utama dari penerapan konsep AVL tree adalah untuk menyeimbangkan BST (Binary Search Tree). Tingkat kekompleksan pengunaan AVL Tree hingga log n, dimana BST hanya sampai n saja.

Ciri-ciri AVL Tree mirip seperti BST, hanya dia memerlukan keseimbangan antara subtree kiri dengan kanan, dengan toleransi max selisih kanan-kiri nya =1.

Jika terdapat ketidakseimbangan antara subtree kanan dan subtree kiri yang melebihi selisih 1, maka kita perlu melakukan rebalance, bisa hanya single rotation, maupun double rotation

untuk melakukan pengukuran penyeimbangan, diperlukan pencarian node yang paling terdalam di subtree kiri vs subtree kanan

1. Untuk operasi insertion pada AVL Tree:
      1. pertama masukkan key baru seperti biasa di BST
      2. Jika tidak seimbang antara subtree kiri dengan subtree kanan, maka bisa dilakukan rebalanced,        seperti ilustrasi dibawah

 
Seperti kita lihat, ketika kita memasukkan key "4", maka terjadi ketidakseimbangan di node key 3, maka perlu dilakukan penggeseran node di node "3"




Penyeimbangan, dilakukan pada node yang paling terdalam

Ketidaksesuaian pada subtree bagian kiri dan anak subtree kiri terdalam DAN Ketidaksesuaian pada subtree bagian kanan dan anak subtree kanan terdalam, dapat dilakukan hanya menggunakan single rotation. (paling mudah, cari yang paling terdalam dan lurus tidak bengkok)

Sedangkan, Ketidaksesuaian pada subtree bagian kiri dan anak subtree kanan terdalam DAN Ketidaksesuaian pada subtree bagian kanan dan anak subtree kiri terdalam, dapat dilakukan menggunakan double rotation. (paling mudah, cari yang paling terdalam dan terlihat cabangnya bengkok)

Contoh ilustrasi single rotation (ketika new key 12, barusan dimasukkan kedalam tree)

Terlihat di node 30 terjadi ketimpangan, antara subtree kanan dan subtree kiri, oleh sebab itu, subtree yang terpanjang/terdalam digeser ke arah berlawanan, dan tiap anak node "22" yang terkena geser (27 dan 29), maka diperlukan penataan ulang juga dari atas.

Contoh ilustrasi double rotation (ketika new key 26, barusan dimasukkan kedalam tree)

Rotasi pertama:
Terjadi ketimpangan pada node 30, dimana node terdalam berada di cabang node 22 (cabang bengkok) , maka pertama tama diperlukan penarikan node 27 ke arah berlawanan. Lalu anak dari node 27, perlu penataan ulang dari atas.



Rotasi kedua:
Setelah itu, terjadi ketimpangan di node 30 sebelah kiri, maka perlu ditarik node 27 ke arah berlawanan, dan tiap anak dari node 27 (29), ditata ulang dari atas.





2. Untuk operasi delete pada AVL tree:
     1.  Node yang boleh di delete, adalah node yang hanya memiliki 1 anak saja atau 0 anak
     2. Jika tidak seimbang antara subtree kiri dengan subtree kanan, maka bisa dilakukan rebalanced,       seperti insertion balanced (single rotation maupun double rotation).

Untuk simulasi dan lebih jelasnya, bisa dicoba sendiri menggunakan simulator:
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

Sekian, ringkasan pada pertemuan pembelajaran kali ini. Terima Kasih.