AVL TREE

--- TUGAS BLOG ALGO-BINUS Mingguan ---

  AVL TREE  

-------------------------------------
------------------------------------------------------

1. AVL Tree

AVL Tree atau disebut juga dengan Balance Binary Search Tree (BST) merupakan binary search tree (BST) yang perbedaan tinggi/level dari subtree kiri dan subtree kanan tidak lebih dari 1 node sehingga dapat dikatakan balance.

gambar AVL Tree

2. Kegunaan AVL Tree

Kegunaan AVL Tree adalah untuk memudahkan pencarian data atau operasi dalam Binary Search Tree sehingga mempercepat dan memperingan kerja program.

3. Single Rotation

Single rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar berikut.

T1, T2, dan T3 adalah subtree yang urutannya harus seperti demikian serta height- nya harus sama (≥ 0). Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image) gambar diatas.

4. Double Rotation

Double rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar berikut. 

T1, T2, T3, dan T4 adalah subtree yang urutannya harus seperti demikian. Tinggi subtree T1 harus sama dengan T4 (≥ 0), tinggi subtree T2 harus sama dengan T3 (≥ 0). Node yang ditambahkan akan menjadi child dari subtree T2 atau T3. Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image) gambar diatas.

5. Operasi Insertion

Secara umum, operasi insertion pada AVL sama seperti insertion pada BST. Namun pada AVL Tree, 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

– Kasus 1 dan 2 dengan single rotation
– Kasus 3 dan 4 dengan double rotation

Contoh – Single Rotation: Jika suatu Tree diinsert node baru dengan nilai 12, maka akan terjadi ketidak seimbangan dan hal ini terletak pada posisi root

Contoh – Double Rotation : Jika terdapat sebuah tree yang kemudian dilakukan insertnode 26. Maka akan terjadi ketidak seimbangan, sehingga terlihat dari bentuknya dapat diselesaikan dengan kasus 4.

6. Operasi Deletion

Ada 2 kasus yang biasanya terjadi saat operasi delete dilakukan, yaitu :
–Kasus 1: Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.
- Kasus 2: 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 :

-------------------------------------------------------------------------------------------------------------

Referensi:

• Power Point AVL Tree
• https://www.geeksforgeeks.org/avl-tree-set-1-insertion/
• https://socs.binus.ac.id/2016/12/20/insertion-avl-tree/
• https://socs.binus.ac.id/2017/05/15/deletion-avl-tree/
• http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html

-------------------------------------------------------------------------------------------------------------

Berikut adalah tugas mingguan membuat blog berisi rangkuman materi AVL Tree yang telah saya pelajari.
Sekian,

---Terima kasih.---

   Nama: Felina Suryadi                  

   NIM: 2301914604                        

   Kelas Besar: CB01                        

-------------------------------------------------------------------------------------------------------------