Monday, May 18, 2020

Heap and Trie

Heap
Heap adalah data structure yang spesial dimana ia tree-based yang treenya adalah complete binary tree.
Array to Heap
Biasanya Heap dibagi menjadi dua yakni,
Max-Heap dan Min-Heap
Min & Max
Pada Max-Heap key pada root harus lebih besar daripada key semua childnya. Begitu juga untuk childrennya yang menjadi parent harus lebih besar daripada childrennya.
Pada Min-Heap key pada root harus lebih kecil daripada key semua childnya. Begitu juga untuk childrennya yang menjadi parent harus lebih kecil daripada childrennya.

Insertion
Saat kita meng-insert data, data akan dimasukan di index terakhir pada array heap tersebut lalu data akan dibandingkan dengan parentnya, jika kondisi Min/Max Heap dilanggar maka data tersebut akan dipindahkan ke tempat parentnya (Up-Heap).

Deletion
Saat kita meng-delete data pada heap, maka root dari heap akan terhapus, lalu array heap terakhir akan langsung menggantikan root yang terdelete. Lalu data tersebut akan di bandingkan dengan childnya, jika kondisi Min/Max Heap dilanggar maka data tersebut akan dipindahkan ke tempat childnya (Down-Heap).

Trie
Trie adalah data structure yang efisien pada bidang re Trieval data. Bentuk trie sendiri berupa tree yang tiap nodenya di isi dengan karakter.
Trie | (Insert and Search) - GeeksforGeeks
Trie
Root pada Trie dapat dikosongkan ataupun di isi dengan karakter. Lalu kegunaan trie salah satunya adalah pada searching.

Referensi:
https://www.geeksforgeeks.org/heap-data-structure/
https://www.geeksforgeeks.org/binary-heap/
https://www.geeksforgeeks.org/trie-insert-and-search/

No comments:

Post a Comment