Perbedaan Tree dan Linked list : Tree tidak linear (kecuali skewed tree) sedangkan Linked list adalah linear, Tree mempunyai banyak relasi seperti Siblings, Parent, Children, Ancestor, Descendant, Root , Leaf , sedangkan Linked list hanya mempunyai Head & Next(Singly) & Head, Tail, Next, Prev(Doubly).

Balanced Binary Search Tree : Binary Search Tree mempunyai algoritma Search yang sangat cepat, namun jikalau tree tidak balance contoh: Skewed BST , dan yang di search adalah leaf node dari BST tersebut , maka search akan tetap berjalan Linear.

Height dan Level pada Tree :
Height adalah tinggi dari sebuah tree , dimulai dari 1 (leaf) , Minimum height of binary tree of n nodes is ²log(n)
Level adalah jarak dari root ke nodes yang dituju , level pada root adalah 0 dan children dari root berlevel 1 , dan seterusnya

Tujuan Balanced Binary Search Tree : Meminimalisasi Height agar dapat mendekati minimum height dari BST sehingga didapatkan algoritma search yang efisien dan kompleksitasnya tetap minimum (O(log(n))). Dapat kita lihat pada tabel dibawah .

http://bigocheatsheet.com/

Berdasarkan tabel diatas, O(log n) dengan elemen < 100 maka operasi yang dibutuhkan sangatlah minimum.

AVL TREE

AVL Tree : berasal dari algoritma G.M.Adelson-Veleskii dan E.M Landis , salah satu algo yang membuat Binary Search Tree menjadi balance.

AVL Tree merupakan BST dengan tambahan algoritma pada:
-Input
-Delete

kedua tambahan diatas digunakan agar Tree menjadi balance.

AVL Tree merupakan algoritma balancing pertama yang pernah dibuat.

AVL Tree dapat diimplementasikan dengan menggunakan Height dari node” nya. Agar tetap balance, antara height kiri dan kanan(siblingnya) harus tetap seimbang(dihitung dari bawah (leaf) dan height diambil yang terbesar).

Leaf node mempunyai height = 1 & Tidak ada node berarti height = 0

Maksimum toleransi selisih antara height kiri dan kanan adalah 1 , jikalau selisih >1 maka parent dari node node tersebut dianggap unbalance.

AVL Tree dikatakan violated apabila saat melakukan input terakhir , tree menjadi Unbalance. Untuk itu diperlukan balancing.

Algoritma balancing dikelompokkan menjadi 2:
– Single Rotation
– Double Rotation

Single rotation dilakukan apabila node yang membuat violated(node input terakhir) berada di Kiri Kiri(LL) ataupun Kanan Kanan(RR) ataupun descendant dari LL/RR node yang terviolated.

contoh:  LL

digunakan single rotation yaitu dengan memutuskan right children dari node 4 (dalam contoh ini kosong/tidak ada), lalu menjadikan 4 sebagai root , lalu menjadikan 6 sebagai anak kanan dari 4. maka akan terbuat sebuah BST yang baru dan balance. lalu anak kanan dari node 4(dalam hal ini tidak ada) akan dijadikan anak kiri node 6.
HASIL :

Double rotation harus dilakukan apabila node yang membuat violated(node input terakhir) berada di Kiri Kanan(LR) ataupun Kanan Kiri(RL) ataupun descendant dari LR/RL node yang terviolated.

Cara melakukan double rotation pada LR dilakukan dengan 2 step :
***Step1***
-Mencopotkan Left children pada node R(node ke 3 dari node yang violated)
-Menempatkan node ke 3 diatas posisi node ke 2 , Right children tetap tertempel di node 3
-Menempatkan Left children dari node ke 3 menjadi Right children dari node ke 2(node ke 2 sudah berada di bawah node ke 3).
***Step2***
-Setelah step 1 telah selesai dijalankan maka akan menjadi LL , lakukan cara single rotation.

=> Untuk double rotation RL menggunakan cara yang sama , namun yang dicopotkan adalah Right children pada node ke 3 dari node violated. tetap ditempatkan diatas posisi node ke 2(left children tetap tertempel). menempatkan right children yang sudah dicopot menjadi left children dari node ke 2.

DELETION

Untuk mendelete node dilakukan cara yang sama dengan deletion pada BST , namun deletion di AVL dapat menyebabkan tree yang sudah balance menjadi tidak balance. Untuk itu diperlukan rebalancing dengan cara rekursif jika ada yang tidak balance dari node yang di delete menuju ke root.

Rebalancing dapat dilakukan berkali kali selama AVL tree masih belum balance

Guest Lecturer by Sir. Selvakumar Manickam , materi sudah terangkum diatas

www.skyconnectiva.com www.binus.ac.id