AVL Tree

Halo, setelah beberapa lama tidak posting karena masa UTS. akhirnya tugas ini datang lagi. setelah 2 minggu UTS yg cukup berdarah-darah, akhirnya aku bisa menyelesaikan semua soal. gatau sih,bener banyak apa bonyok banyak yang penting udah lewat :)

kali ini, kita bakalan bahas materi yang lebih advanced. kt akan membahas tentang AVL TREE.
apa itu avl tree?

sebuah pohon biner terurut yang dapat menyeimbangkan dirinya sendiri. Pada sebuah pohon AVL, tinggi dari dua anak sub pohon dari simpul apapun memiliki perbedaan paling besar 'satu'. 

AVL Tree ditemukan oleh Adelson-Velskii dan Landis

Lookup, penyisipan (insertion), dan penghapusan (deletion) semuanya memerlukan O(logn) kali dalam kasus biasa dan kasus terburuk. 

Penambahan (additions) dan penghapusan membutuhkan pohon tersebut untuk menyeimbangkan kembali dirinya melalui rotasi pohon satu kali atau lebih.

cara perurutannya yaitu sebelah kiri nilai yang paling rendah sedangkan sebelah kanan nilai paling besar dari nilai utamanya (root),left<root<right.

Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :

anggap T adalah node yang harus diseimbangkan kembali

– Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)

– Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)

– Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)

– Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi
– dengan single rotation
– Kasus 3 dan 4 dengan double rotation

ini adalah unbalanced tree.

setelah di rebalance menjadi AVL Tree

Ada 2 kasus yang biasanya terjadi saat operasi delete dilakukan, yaitu :

– Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.

• Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1.
• anggap T adalah node yang harus diseimbangkan kembali
  – Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
  – Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
  – Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
  – Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)
  

Berikut contoh dalam menghapus node AVL Tree, terdapat AVL Tree yang kemudian di hapus node 60. Dengan gambaran sebagai berikut :

Yang akan menggantikan posisi node 60 adalah node 55. Akan terjadi ketidak seimbangan. Dengan tampilan sebagai berikut :

Maka akan dilakukan single rotation pada node 55 dengan kasus ketidak seimbangan pada kasus no. 2. Dengan tampilan setelah dilakukan single rotation sebagai berikut :

Ketika sudah dilakukan single rotation dan dilakukan kembali perbedaan tinggi / level maksimal 1 ternyata terdapat ketidak seimbangan yang terjadi. Sehingga diperlukan double rotation dengan kasus no. 4. Sehingga hasil dari rotasi yang dilakukan adalah sebagai berikut :

source :
https://socs.binus.ac.id/2016/12/20/insertion-avl-tree/
https://socs.binus.ac.id/2017/05/15/deletion-avl-tree/