Heap & Tries

Heap

Heap merupakan suatu tree-based data structure yang dimana merupakan sebuah tree yang hampir komplit yang melengkapi syarat heap property (Setiap nodepada sebuah tree yang memiliki key yang lebih besar, lebih kecil, atau sama dengan key dari parentya). Terdapat cara penentuan parent dan child pada heap, yaitu sebagai berikut:

Misalkan x adalah suatu elemen (Angka merah menandakan array)

- Parent : x / 2, cth : 4 / 2 = 2

- Left Child : x * 2, cth : 4 * 2 = 8

- Right Child : (x * 2) + 1, cth : (4 * 2) + 1 = 8 + 1 = 9

Terdapat 2 macam heap yaitu Max heap dan Min heap.

• Max Heap : Pada max heap terdapat key yang berada pada root node yang harus lebih besar daripada key anak - anaknya.

 Jika dilakukan max heap insertion:
- Node baru akan diinsert pada array index selanjutnya (Pada contoh diatas left child dari node 10)
- Akan dibandingkan node yang baru dan value node diatasnya, bila lebih besar diswap (Dilakukan sampai value parent lebih besar

Jika dilakukan max heap deletion:
- Delete node yang ingin dihapus
- Node digantikan node yang berada di paling kanan bawah (Jika node yang dihapus memiliki left atau right child)
  - Jika heap property sudah benar maka selesai.
  - Jika value node pengganti >= node parentnya maka diswap, lalu diulang cek sampai heap property.
  - Jika tidak, tukar dengan node child paling besar.

• Min Heap : Pada min heap terdapat key yang berada pada root node yang harus merupakan nilai minimum diantara key anak - anaknya.

Min heap deletion dan insertion sama dengan max heap hanya lebih besar menjadi lebih kecil

• Max-Min Heap : Merupakan binary tree komplit yang berisi level min (genap) dan max (ganjil) 

Jika dilakukan max-min heap insertion:

- Insert node baru pada index selanjutnya (Contoh diatas diinsert pada right child 10)

- Dilakukan proses heapify (Mengecek node yang baru dengan parentya dan grandparentnya sesuai dengan level)

- Proses dilakukan sampai heap property benar

Trie

Sebuah trie adalah tree mirip data structure yang menyimpan node huruf alfabet.

Insertion pada Trie
Semua karakter yang diinsert termasuk sebagai node trie individu. Children node merupakan suatu array of pointers terhadap trie node diatasnya. Karakter key merupakan index terhadap childrennya. Jika key yang diinput baru atau merupakan tambahan dari key yang sudah ada, maka diharuskan membuat node baru dari key tersebut dan tandai node selanjutnya sebagai EOW (End of Word).

Kata - kata yang terdapat pada gambar diatas adalah

- CAR

- CAB

- CAN

Aplikasi dari trie adalah

- Autocomplete 

- Search engine browser

- Bubble words