Struktur Data pertemuan 6: Balanced Binary Search Tree & Guest Lecture

Regina

1901457321

Hari: Rabu, 11/05/2016

Kelas: CD01-CL

Lecturer: Rulyna ( D4689 ) dan Henry Chong ( D4460 )

Tree dengan height seminimal mungkin dengan kompleksitas O(log n) disebut Balanced Binary Search Tree, contohnya adalah AVL Tree dan Red Black Tree.

AVL TREE

Nama AVL merupakan kependekan dari nama penemu AVL Tree, yaitu G.M Adelson-Veleskii dan E.M Landis pada tahun 1962.

Balance factor (merah) merupakan selisih height anak kiri dan anak kanan. Balance factor pada tiap node maksimalnya adalah 1. Lebih dari 1 merupakan pelanggaran(violation).

Contoh dimana Balance factor pada node 17 lebih dari 1 sehingga,  pelanggaran (violation) terjadi.

Operations pada AVL Tree:

·         Insertion

·         Deletion

AVL Tree operation: Insertion

Untuk AVL Tree, iap kali kita menambahkan node, kita harus menghitung height dan balance factor tiap node untuk menemukan AVL violation. Dan jika ketemu violation, maka kita harus me-rebalance tree.

Misalkan, violation terjadi di node T. Ada 4 macam kasus :

·         Case LL : T – Left – Left

·         Case RR : T – Right –Right

·         Case LR : T – Left – Right

·         Case RL : T – Right – Left

Dimana LL dan RR diseimbangkan dengan single rotation dan LR dan RL diseimbangkan dengan double rotation.

Single Rotation:

·         LL

·         RR

Double Rotation:

AVL Tree operation: Deletion

Hasil akhir yang sudah di-rebalance

SESI II

Pada hari Rabu, 11 Mei 2016, tepatnya pada sesi ke-2, kami kedatangan dosen tamu dari University of Science, Malaysia yaitu, Bpk. Selvakumar Manickam, PhD.

Kami diajarkan banyak tentang AVL Tree, m-ary trees, binary tree dan binary search tree, kompleksitas pada tiap tree.

Beliau pun menunjukkan data kompleksitas beberapa struktur data.

 

untuk menyatakan keefektifan sebuah algoritma.