Heaps & Tries

Heaps

Heaps adalah binary tree yang terdiri dari 3 jenis:
- min heap: setiap node lebih kecil daripada childrennya.
- max heap: setiap node lebih besar daripada childrennya.
- min-max heap: node terkecil terdapat pada root dan node terbesar berada pada children root.

operation dalam heap (tergantung jenis heap):
find-min/max  : mencari node terkecil/terbesar.
insert  : memasukan node kedalam heap.
delete-min/max: menghapus elemen terkecil/terbesar.

Representasi heap dalam array:

Rumus lokasi node heap dalam suatu array (sudah pasti):

-Parent(x) = x / 2

-Left-child(x) = 2 * x

-Right-child(x) = 2 * x + 1

Tries

Tries adalah data structure yang efisien dan menggunakan waktu pencarian selama banyaknya character yang dicari. Root node pada suatu tries selalu kosong untuk menggabungkan seluruh children dari root.



Tries digunakan dalam aplikasi search and spell checker.