Heap dan Tries

Heap

Heap adalah struktur data berbasis pohon khusus di mana pohon itu adalah pohon biner lengkap. Secara umum, Heap terdiri dari dua jenis, yaitu:

• Max-Heap: Dalam Max-Heap node root harus paling besar di antara node yang ada di semua children-nya. Properti yang sama harus benar secara rekursif untuk semua subtree di Tree tersebut.

• Min-Heap: Dalam Min-Heap node root harus paling kecil di antara node yang ada di semua children-nya. Properti yang sama harus benar secara rekursif untuk semua subtree di Tree tersebut.

Insert

Untuk melakukan Insert, kita harus melakukan operasi up-heap.

1. Tambahkan elemen pada level bawah Heap,
2. Bandingkan elemen yang baru dengan parentnya. Jika berada di urutan yang benar, pembandingan berhenti.
3. Jika tidak, swap elemen dengan parent dan kembalikan ke langkah sebelumnya.

Delete

Untuk melalkukan delete, kita harus melakukan operai down-heap.

1. Ganti root Heap dengan elemen terakhir pada level terakhir.
2. Bandingkan root baru dengan children-nya. Jika berada di urutan yang benar, pembandingan berhenti.
3. Jika tidak, swap elemen dengan salah satu children dan kembali ke step sebelumnya.

Trie

Trie adalah struktur data pencarian informasi yang efisien. Menggunakan Trie, kompleksitas pencarian dapat dibawa ke batas optimal (panjang kunci). Jika kita menyimpan node dalam sebuah Binary Tree, BST yang seimbang akan membutuhkan waktu yang proporsional dengan M * log N, di mana M adalah panjang string maksimum dan N adalah jumlah kunci dalam tree. Dengan menggunakan Trie, kita dapat mencari node dalam waktu O (M).

Insert

Insert node ke Trie sangat sederhana. Setiap karakter node input dimasukkan sebagai simpul Trie individual. Perhatikan bahwa children adalah array pointer ke node Trie level berikutnya. Karakter node bertindak sebagai index ke dalam array children. Jika node input adalah baru atau ekstensi dari kunci yang ada, kita perlu membangun simpul node yang tidak ada, dan menandai akhir kata untuk simpul terakhir. Jika kunci input adalah awalan dari kunci yang ada di Trie, kita cukup menandai simpul terakhir kunci sebagai akhir kata. Panjang node menentukan kedalaman Trie.

Sumber:

- geeksforgeeks.org

- furqonubd.wordpress.com