HEAP & TRIES

I. PENGERTIAN HEAP

Heap merupakan sebuah complete binary tree yang memiliki beberapa sifat tertentu.

Ada 3 jenis :

1. Min-Heap

Root paling atas memiliki nilai terkecil.

2. Max-Heap

Kebalikan dari min-heap. Root paling atas memiliki nilai terbesar.

3. Min-Max Heap

Kondisi antar level bergantian antara minimum dan maximum. Dimulai dengan level paling atas (0) bernilai paling minimum dan level 1 bernilai paling maksimum.

II. INSERTION

1. Min-Heap

1. Insert nilai baru sebagai node terakhir dari heap.
2. Bandingkan nilai baru yang diinsert dengan parent-nya. Jika lebih kecil dari parent, maka tukar nilainya.
3. Swap dihentikan jika nilai parent-nya lebih kecil dari current node atau jika current node adalah root.

2. Max-Heap

Cara menginsert sebuah nilai baru pada Max-Heap sama dengan Min-Heap. Perbedaannya adalah nilai parent lebih besar daripada nilai child.

3. Min-Max Heap

1. Insert nilai baru sebagai node terakhir dari heap.
2. Jika nilai baru ada pada Min-Level dan parent dari nilai  baru  lebih kecil dari nilai yang diinsert, maka nilai baru ditukar dengan parentnya.
3. Jika nilai baru ada pada Max-Level dan parent dari nilai baru lebih besar dari nilai yang diinsert, maka nilai baru ditukar dengan parentnya.
4. Upheapmin : Bandingkan nilai dari current node dengan nilai dari grand-parent. Jika nilai dari current node lebih kecil dari parent-nya, maka keduanya ditukar.
5. Upheapmax : Bandingkan nilai dari current node dengan nilai dari grand-parent. Jika nilai dari current node lebih besar dari parent-nya, maka keduanya ditukar.

III. PENGERTIAN TRIES

Tries adalah tree struktur data terstruktur yang digunakan untuk menyimpan array asosiatif, biasanya string.

Root berisi kosong dan setiap node berisi 1 huruf.

Kata-kata yang ada pada tries diatas : ALGO, API, BOM, BOS, BOSAN, BOR.

Referensi :
https://mikesebastian.weebly.com/blog/category/struktur-data
http://prillysia.blog.binusian.org/tag/tries/






Dibuat oleh :
Livia Leonita - 2301905726
CB 01