HEAPS AND TRIES

May 11, 2020

HEAPS

Dalam ilmu komputer, sebuah heap adalah struktur data yang berdasarkan konsep struktur data pohon.

Contohnya jika P adalah parent dari node C, maka kunci (nilai) dari P adalah lebih besar dari atau sama dengan (dalam max heap) atau kurang dari atau sama dengan (dalam min-heap) kunci C. Node di "atas" dari struktur heap (parent) disebut root node.

1. MIN HEAP

Di dalam konsep Min Heap, node yang berada dibawahnya atau parent nilainya akan lebih kecil dibandingkan dengan node anaknya. Maka dapat disimpulkan node root merupakan node dengan nilai paling kecil , dan salah satu node dari leaf node merupakan node yang nilainya paling besar.

Contoh:

a. Find-Min

Minimum node terletak pada root

b. Insertion pada Min-heap

· Insert node selalu berurutan dari level paling rendah dengan urutan left ke right.

· New node selalu menjadi leaf node.

· Sesuaikan dengan heap properties secara rekursif.

c. Deletion pada Min-heap

· Node yang dihapus selalu root karena merupakan node paling kecil, lalu diganti dengan node yang paling terakhir di-insert.

· Sesuaikan dengan heap properties secara rekursif.

2. MAX HEAP

Konsep Max Heap hanya berbeda sedikit , perbedaannya hanya ada di node paling atas akan memiliki node dengan nilai terbesar dan salah satu node dari leaf node akan memiliki nilai yang terkecil.

Insertion dan deletion pada max heap disesuaikan dengan properties max heap.

3. MIN-MAX HEAP

Konsep Min Max Heap adalah level root akan bernilai minimum, selanjutnya akan bernilai maximum, dan seterusnya. Nilai terkecil berada di root dan nilai terbesar berada di salah satu node pada level setelah root. Level min hanya dapat dibandingkan dengan level min, dan sebaliknya.

Contoh:

· Insert node sesuai urutan, lalu cek upheap lalu sesuaikan dengan properties level. Umumnya dilakukan penyesuaian rekursif dengan urutan sebagai berikut.

a) Parent

b) Grand Parent

· Deletion selalu dilakukan pada root, lalu sesuaikan dengan downheap sesuai properties. Umumnya dilakukan penyesuaian secara rekursif dengan urutan sebahai berikut.

a) Grand Child

b) Child (grand child disesuaikan dengan parentnya)

TRIES

Tries atau prefix tree adalah suatu pohon struktur data yang terurut yang menyimpan data array, biasanya string. Kata tries diambil dari kata RETRIEVAL, karena tries dapat menemukan kata tunggal dalam kamus dengan hanya awalan katanya saja.

Tries sudah diterapkan ke banyak hal dalam kehidupan sehari-hari, contohnya pada web browser. suatu web browser dapat mengira atau mensugestikan kata-kata yang mungkin kita maksud saat kita mengetik huruf pertamanya saja. (autocomplete)

Kemudian selain itu juga pada spell checker, spell checker dapat mengetahui spelling kata yang tepat saat kita melakukan kesalahan dalam pengetikan. (autocorrect)

Tries adalah suatu tree dimana setiap vertex/pathnya menggambarkan suatu kata, rootnya kosong.

Gambarannya :