ringkasan trie

Trie (Prefix Tree)
Pengertian Trie
Istilah Trie berasal dari kata Retrieval, karena trie dapat menemukan satu kata dalam kamus, dengan hanya awalan dari sebuah kata.
Trie atau Prefix Tree adalah sebuah ordered tree data structure, yang digunakan untuk menyimpan sebuah array asosiatif di mana key biasanya berupa string. Tidak seperti Binary Search Tree yang lainnya, tidak ada node di tree yang menyimpan key yang terkait dengan node itu; Sebaliknya, posisinya dalam tree menunjukan dengan apa key itu terkait. Semua keturunan dari sebuah node memiliki prefix umum dari string yang berhubungan dengan node itu, dan root dikaitkan dengan string kosong. Nilai biasanya tidak berhubungan dengan setiap node, hanya dengan daun dan node bagian dalam yang saling berhubungan pada key tujuannya.

Nilai biasanya tidak berhubungan dengan setiap node, hanya dengan daun dan node bagian dalam yang saling berhubungan pada key tujuannya.

nah mungkin jika anda masih pada bingung perhatikan contoh di bawah ini

Contoh Trie

Contoh Aplikasi dari Trie:
- Fitur Spell Checker yang dapat mengecek setiap kata yang anda ketik ada dalam kamus/ dictionary.
- Pemberian saran/ koreksi dari Spell Checker, bila ada kata yang salah ketik.
- fitur Auto Complete Text yang dapat memberikan beberapa kemungkinan tentang teks yang anda akan ketik.

dalam pencarian google maka dengan secara otomotis dia akan men suggest kita dalam pencarian kita selanjutnya

autocomplete text

Trie
- Trie adalah sebuah pohon dimana setiap vertex mewakili satu kata atau prefiks.
- Root merupakan karakter yang kosong (”).
- Sebuah vertex yang k ujung jarak dari root memiliki prefix yang terkait dengan panjang k.
Misalkan A dan B adalah dua vertex dari trie dan asumsikan A adalah orang tua langsung dari B, maka B harus memiliki prefix terkait dengan A.

Struktur Trie