Trie (dibaca "try") adalah tree untuk menyimpan kata, satu huruf per node. Tree adalah struktur bercabang: ada satu node paling atas (root), dan tiap node bisa punya beberapa anak. Di trie, kata yang awalannya sama memakai jalur yang sama dari root, mirip kamus yang dibuka huruf demi huruf: b, be, bel, lalu semua kata berawalan "bel" ada di situ.
🧪 Tebakan cepat: trie berisi kata belajar, beli, dan belanja. Kalau kamu mencari kata utuh "bela", jawabannya true atau false? Tebak dulu, jawabannya ada di bagian "search dan startsWith: gunanya isEnd".
Satu huruf per node
Waktu kata dimasukkan, trie turun dari root huruf demi huruf. Node huruf yang sudah ada dipakai ulang, yang belum ada dibuat baru:
| insert | Node dipakai ulang | Node baru |
|---|---|---|
| belajar | gak ada | 7: b, e, l, a, j, a, r |
| beli | 3: b, e, l | 1: i |
| belanja | 4: b, e, l, a | 3: n, j, a |
Totalnya 11 node untuk 18 huruf, karena awalan "bel" dipakai bersama ketiga kata, dan "bela" dipakai bersama belajar dan belanja. Makin banyak kata berawalan sama, makin banyak node yang dihemat.
class TrieNode {
constructor() {
this.children = {};
this.isEnd = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (const huruf of word) {
if (!node.children[huruf]) {
node.children[huruf] = new TrieNode();
}
node = node.children[huruf];
}
node.isEnd = true;
}
search(word) {
let node = this.root;
for (const huruf of word) {
if (!node.children[huruf]) return false;
node = node.children[huruf];
}
return node.isEnd;
}
startsWith(prefix) {
let node = this.root;
for (const huruf of prefix) {
if (!node.children[huruf]) return false;
node = node.children[huruf];
}
return true;
}
}
const trie = new Trie();
trie.insert("belajar");
trie.insert("beli");
trie.insert("belanja");
console.log(trie.search("beli")); // true
console.log(trie.search("bel")); // false
console.log(trie.startsWith("bela")); // true
console.log(trie.startsWith("bo")); // false
TrieNodepunya dua hal:children, objek yang memetakan huruf ke node anaknya, danisEnd, tanda bahwa sebuah kata berakhir di node ini.insertturun dari root lewatchildren. Kalau anak untuk huruf itu belum ada, dibuat dulu dengannew TrieNode(). Di node huruf terakhir,isEnddiisitrue.searchturun dengan cara yang sama. Ada huruf yang gak punya anak berartifalse. Kalau semua hurufnya ada, jawabannyanode.isEnd.startsWithsama persis, tapi di akhir selalutrue: awalannya cukup bisa ditelusuri sampai habis.
Ketiganya O(m), m = panjang kata atau awalannya: kata dua kali lebih panjang, langkahnya dua kali lebih banyak. Banyaknya kata di dalam trie gak berpengaruh.
search dan startsWith: gunanya isEnd
Jalur b, e, l, a ada di trie, karena belajar dan belanja lewat situ. Tapi gak ada kata yang berakhir di huruf a itu, jadi isEnd-nya false. Hasilnya search("bela") menjawab false, sedangkan startsWith("bela") menjawab true. Itu jawaban tebakan tadi: awalan yang ada belum tentu kata.
Kebalikannya juga bisa: sebuah kata bisa jadi awalan kata lain. Masukkan "main" dan "mainan", maka search("main") dan startsWith("main") sama-sama true, karena node n terakhir di "main" punya isEnd sekaligus punya anak.
Kapan pakai trie
Trie paling cocok untuk autocomplete (saran kata waktu mengetik) dan pencarian awalan: turun ke node awalannya, dan semua kata yang cocok ada di bawah node itu. Cek ejaan juga cocok: search memastikan katanya ada, startsWith mencari kata dengan awalan yang sama. Kalau kamu cuma perlu mengecek kata utuh, Set lebih sederhana dan lebih hemat memori.
⚠️ Jebakan yang sering ketemu
- Lupa
isEnd = truedi akhirinsert. Semuasearchjadifalse, karena gak ada node yang ditandai sebagai akhir kata. searchyang menjawabtruebegitu jalurnya ada. Itu cara kerjastartsWith.searchharus mengembalikannode.isEnd.- Membuat node baru tanpa mengecek.
node.children[huruf] = new TrieNode()tanpaifmenimpa node lama, dan kata yang sudah dimasukkan hilang. - Huruf besar dan kecil beda jalur. "Beli" dan "beli" dianggap dua kata. Ubah dulu pakai
toLowerCase()sebeluminsertdansearch.
TL;DR: Trie menyimpan kata satu huruf per node, dan kata berawalan sama berbagi node. insert turun huruf demi huruf, membuat node yang belum ada, lalu menandai node terakhir dengan isEnd = true. search mengembalikan node.isEnd, jadi awalan seperti "bela" bukan kata; startsWith cukup menelusuri semua hurufnya lalu true. Semuanya O(panjang kata). Pakai trie untuk autocomplete dan pencarian awalan; untuk cek kata utuh saja, Set sudah cukup.
