heap and tries

Heap & Tries

Heap Property terbagi menjadi 2, yaitu Min Heap dan Max Heap. Konsep Min Heap, di mana parent node lebih kecil dari child nodenya, sebaliknya dalam konsep Max Heap parent nodenya lebih besar dari child nodenya.
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.

Insertion dalam Min Heap:
Jika kita akan menginsert sebuah angka, maka kita harus meletakkan node tersebut di tempat setelah terakhir. Lalu, kita cek kondisi dengan parent nya, jika node tersebut lebih besar dari parentnya maka di swap, lakukan cara tersebut sampai root.

Deletion dalam Max Heap:
Jika kita akan menghapus suatu node, maka node yang akan menggantikan adalah node yang paling terakhir. Setelah itu cek kondisi dengan child nya, jika node tersebut lebih besar dari child nya maka di swap, lakukan cara tersebut sampai leaf.

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.

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.

Insertion dan Deletion sama seperti Min Heap atau Max Heap namun, pengecekan kondisi hanya dapat dilakukan di level sesama min atau max.


Tries Concept
Berasal dari kata reTRIEval yang berarti untuk menyimpan asosiatif array dan jika dalam aplikasinya trie concept ini seperti auto-complete.

Properties pada tries:

• Setiap vertex/node merepresentasikan satu huruf
• Root merepresentasikan karakter kosong
• Aplikasi pada trees adalah fitur auto-complete yang ada pada web-browser