Data Structures - pertemuan 8

Regina
1901457321

Hari: Rabu, 25/05/2016

Kelas: CD01-CL

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

HEAP

Heap merupakan complete binary tree berdasarkan struktur data yang memenuhi syarat heap. Ada 3 jenis heap:

·         Min Heap

·         Max Heap

·         Min-Max Heap

Bedanya min heap dan max heap

Pengaplikasian heap adalah pada priority queue (Selection, Djiktra, Prim) dan heap sort ( O (n.lg(n)) ). Heap pada priority queue terdiri atas find, insert dan delete. Dapat di-implementasikan dengan menggunakan linked-list. Tapi, lebih gampang menggunakan array. Index array pada heap mulai dari 1, membiarkan index ke-0 blank/tidak digunakan.

Untuk mencari index node:

a.      Parent(x) = x/2

b.      Left child(x)= 2*x

c.       Right child (x) = 2*x+1

Min Heap

·         Tiap elemen node nya lebih kecil daripada elemen anak-anaknya.

·         Elemen yang paling kecil berada di root

·         Elemen yang paling besar berada di salah satu node leaf.

·         Data dimasukkan secara urut dari kiri ke kanan, level selalu sama.

Insert 20:

Insert 20 dengan cara mengurutkan dari kiri ke kanan. Lalu, bandingkan dengan parentnya apakah 20 lebih besar atau lebih kecil dari parent. Karena min heap, jika parent nya lebih besar, maka tukarlah parent dengan childnya. Sehingga 20 menjadi parent yang memiliki anak 32 dan 28.

Insert 5:

Seperti insert 20 di atas, karena 5 merupakan node yang paling kecil, sehingga ia menjadi root pada tree tersebut dengan cara membandingkan dengan parent parentnya.

Delete 7:

Deletion pada min heap menggunakan downheap. Dimana ketika root di dilete, maka node yang terakhir di insert akan menggantikan parent, lalu dibandingkan lagi antara parent dengan childnya, lalu lakukan pertukaran downheap.

Delete 7 dan gantikan dengan node yang terakhir di-insert, yaitu node 28. Lalu, bandingkanlah lagi antara parent dengan child mana yang lebih besar, mana yang lebih kecil dengan tetap mengurut dari kiri ke kanan. Sampai node terkecil menjadi root.

Kompleksitas min heap:

·         Find min = O(1)

·         Insert = O(log(n))

·         Delete min = O(log(n))

Insert dan delete min tergantung pada ketinggian tree nya.

Max Heap

Seperti min heap tapi kebalikannya. Jika min heap rootnya merupakan node terkecil, root pada max heap merupakan node yang paling besar. Sehingga, elemen nodenya lebih besar dibandingkan dengan elemen anak-anaknya.

Min Max Heap

Min max heap merupakan gabungan dari min heap dan max heap.

Nilai terkecil berada pada root sebuah tree tersebut. Node terbesar berada di salah satu anak dari root entah kanan atau kiri. Node terbesar dapat berada di root jika hanya ada 1 node yang berada di heap.

Insert 1:

Angka 1 di insert. Karena 1 berada di level max dan 1 lebih kecil dari 10, maka lakukan penukaran.

Setelah 1 dan 10 ditukar, bandingkan lagi dengan root apakah sudah lebih kecil dari 1. Jika ya, tukar.

Insert 85

Insert 85 dan bandingkan dengan parentnya. Karena parent 80 lebih kecil dari 85, lakukan penukaran. Bandingkan lagi dengan level 2 – max. Karena 90 lebih besar dari 85 maka tidak terjadi penukaran.

 Delete 1

Karena 1 di delete, maka digantikan oleh 80, node yang terakhir di insert, lalu bandingkan dengan anak-anaknya.

Karena 2 masih lebih kecil dari 80, maka lakukan penukaran.

Delete pada max heap memiliki konsep yang sama dengan min heap.

TRIES

·         Tries adalah sebuah tree dimana setiap vertex merepresentasikan sebuah kata atau sebuah prefix.

·         Struktur data yang menyimpan associative array

·         Root : (‘’)

·         Tries dapat digunakan pada fitur auto complete pada web browser seperti pada search engine, google.

HASHING

Merupakan table (array) dimana kita menyimpan string yang original. Dimana index table diambil dari hashed key dan valuenya adalah string original.

Atan di simpan ke h[0] karena “a” merupakan huruf pertama sehingga disimpan pada index ke-0. Char disimpan di h[2] karena “c” merupakan huruf ketiga dan disimpan pada index ke-2 dan seterusnya.

Pertimbangkan hanya huruf pertama dari tiap string.

            Jika, ada 2 kata dengan huruf depannya sama gunakan cara:

·         Linear Probing

Isi pada h[1] adalah acos. Padahal, acos harusnya di h[0] karena “a”. Tetapi, h[0] sudah ditempati oleh atan. Sehingga, acos harus menempati h[1]. Huruf “a” ada 2 index. Maka step pada acos kita tulis 2 karena ada 2 langkah.

Contoh lagi pada h[6], yaitu ceil, yang seharusnya berada di h[2]. Tetapi, h[2] sudah ditempati oleh char. Dan h[3] sudah ditempati oleh define. Maka, step pada ceil kita tuliskan 5 karena bera 5 langkah dari h[2].

·         Chaining