Heaps and Tries

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.

Di samping merupakan contoh trie. Trie tersebut menunjukan kata: ALGO, API, BOM, BOSAN, BOR.

Tries hanya digunakan dalam node alfabet saja.