Heap adalah Binary Tree khusus yang berbentuk complete. Tapi
bedanya dengan AVL Tree, Heap mempunyai heap property atau kondisi:
·
Max Heap: dimana nilai parent harus lebih tinggi
daripada anaknya
·
Min Heap: Dimana nilai root/puncaknya harus
nilai terkecil dari semua node
Ada juga yang disebut min-max
heap. Heap ini merupakan gabungan dari min heap dan max heap. Heap ini akan
berganti-ganti antara min heap dan max heap di tiap level. Heap ini berguna
untuk mencari nilai min max dalam 1 heap saja.
Insertion
Dalam melakukan inert node dalam
suatu heap, kita lakukan Up-heap. Up-heap akan menaikan node jika nilai node
lebih besar hingga mempunyai urutan yang benar
Kita akan gunakan Min-Heap yang
simpel ini. Peraturan Min-heap adalah jika anak<parent maka anak ganti
tempat sama parent hingga urutannya dari atas ke bawah kecil hingga besar.
Di Heap di atas node 4 dan 5
salah karena parentnya (5) lebih besar daripada node anaknya (4), maka hanya
diharuskan untuk ganti tempat aja. Hingga hasilnya:
Deletion
Dalam deletion, jika ingin
menghapus node akan dilakukan down-heap. Beda dengan Up-Heap, Down -Heap
mengganti node root dengan elemen terakhir pada level terakhir. Contohnya
dengan heap ini.
Heap di atas ini menggunakan
Min-Heap. Jadi jika node yang akan dihilangin 0 maka node penggantinya adalah
nilai terkecil yang ada di level terbawah. Jadi penggantinya adalah 9.
Tapi akan dilakukan up-heap
karena node 9 lebih besar dibanding node 1 maka 9 akan mengganti tempat 1. Dan
Nanti node 2 akan up-heap mengganti 9. Jadi hasil akhirnya:
Trie
Trie adalah struktur data berupa
pohon terurut untuk menyimpan suatu himpunan string dimana setiap node pada
pohon tersebut mengandung awalan yang sama. Sebenarnya kata Tries diambil dari
kata reTRIEval, karena tries menemukan kata tunggal dalam kamus dengan hanya
awalan katanya.
Tries hanya digunakan dalam node
alfabet saja.
