Trie (Pohon Prefiks)
Terakhir diperbarui
Trie (dibaca "try"), atau prefix tree (pohon prefiks), adalah struktur data yang menyimpan himpunan string berdasarkan karakternya: setiap edge diberi label sebuah karakter, dan jalur dari root membentuk sebuah prefiks. Kata-kata yang punya prefiks yang sama berbagi node yang sama, jadi "car", "card", dan "care" semuanya memakai ulang jalur c-a-r. Tekan Putar di atas untuk melihat kata-kata disisipkan satu karakter demi satu karakter, dan hanya bercabang di bagian yang berbeda.
Karena pencarian menelusuri satu node per karakter, mencari kata sepanjang m butuh waktu O(m), berapa pun jumlah kata yang disimpan trie. Itulah yang membuat trie ideal untuk autocomplete, pemeriksaan ejaan, dan pencarian prefiks.
Kompleksitas waktu dan ruang
| Operasi | Kompleksitas | Catatan |
|---|---|---|
| Penyisipan | O(m) | m = panjang kata |
| Pencarian | O(m) | Satu langkah per karakter |
| Query prefiks | O(m) | Telusuri sampai node prefiks |
| Ruang | O(total chars) | Prefiks yang sama disimpan sekali |
Langkah demi langkah (penyisipan)
| Langkah | Apa yang terjadi |
|---|---|
| 1 | Mulai dari node root. |
| 2 | Untuk setiap karakter dalam kata, cari edge anak yang cocok. |
| 3 | Jika ada, ikuti edge itu (memakai ulang prefiks yang sama). |
| 4 | Jika tidak ada, buat node anak baru untuk karakter itu. |
| 5 | Setelah karakter terakhir, tandai node itu sebagai akhir kata. |
Contoh penerapan
Menyisipkan ["car", "card", "care"] ke trie kosong:
| Langkah | Struktur | Aksi |
|---|---|---|
Sisipkan car | root → c → a → r✓ | Belum ada anak yang cocok, jadi buat c, a, r dan tandai r sebagai akhir kata. |
Sisipkan card | root → c → a → r✓ → d✓ | Pakai ulang jalur c-a-r yang sudah ada, lalu buat satu anak baru d dan tandai sebagai akhir kata. |
Sisipkan care | root → c → a → r✓ → {d✓, e✓} | Pakai ulang c-a-r, buat cabang dari r dengan anak baru e, dan tandai e sebagai akhir kata. |
Cari care | root → c → a → r → e✓ | Telusuri c, a, r, e; node terakhirnya ditandai sebagai akhir kata, jadi care ada. |
Cari ca | root → c → a | Jalurnya ada, tetapi a tidak ditandai sebagai akhir kata, jadi ca adalah prefiks, bukan kata yang disimpan. |
Kapan memakai trie
| Pakai saat | Hindari saat |
|---|---|
| Kamu butuh query prefiks atau autocomplete atas sekumpulan string. | Kamu hanya butuh pencarian key utuh: hash table lebih cepat dan lebih ringan. |
| Banyak kata yang disimpan punya prefiks yang sama, sehingga node dipakai ulang. | Key-nya panjang dan jarang tumpang tindih, sehingga membuang satu node per karakter. |
| Kamu ingin key dikembalikan dalam urutan terurut lewat penelusuran. | Memori terbatas: pointer anak di setiap node menambah beban yang besar. |
| Biaya pencarian harus bergantung pada panjang key, bukan ukuran data. | Alfabetnya sangat besar (misalnya seluruh Unicode) dan anak-anaknya disimpan secara padat. |
Kode Trie (Prefix Tree)
Implementasi Trie (Prefix Tree) yang rapi dan siap dijalankan dalam Python, JavaScript, Java, C++, C. Pilih bahasa, salin kodenya, atau buka langsung di Coddy Playground.
Kode Trie (Prefix Tree) dalam Python
Python
1class TrieNode:2 def __init__(self):3 self.children = {}4 self.is_word = False5
6
7class Trie:8 def __init__(self):9 self.root = TrieNode()10
11 def insert(self, word):12 node = self.root13 for ch in word:14 node = node.children.setdefault(ch, TrieNode())15 node.is_word = True16
17 def search(self, word):18 node = self._walk(word)19 return node is not None and node.is_word20
21 def starts_with(self, prefix):22 return self._walk(prefix) is not None23
24 def _walk(self, s):25 node = self.root26 for ch in s:27 if ch not in node.children:28 return None29 node = node.children[ch]30 return node31
32
33trie = Trie()34for word in ["car", "card", "care", "dog"]:35 trie.insert(word)36
37print("search(card): ", trie.search("card"))38print("search(ca): ", trie.search("ca"))39print("starts_with(ca): ", trie.starts_with("ca"))40print("starts_with(do): ", trie.starts_with("do"))41print("starts_with(cat): ", trie.starts_with("cat"))Kode Trie (Prefix Tree) dalam JavaScript
JavaScript
1class TrieNode {2 constructor() {3 this.children = {};4 this.isEnd = false;5 }6}7
8class Trie {9 constructor() {10 this.root = new TrieNode();11 }12
13 insert(word) {14 let node = this.root;15 for (const ch of word) {16 if (!node.children[ch]) node.children[ch] = new TrieNode();17 node = node.children[ch];18 }19 node.isEnd = true;20 }21
22 // Walk the prefix; null when a character is missing23 findNode(prefix) {24 let node = this.root;25 for (const ch of prefix) {26 node = node.children[ch];27 if (!node) return null;28 }29 return node;30 }31
32 search(word) {33 const node = this.findNode(word);34 return node !== null && node.isEnd;35 }36
37 startsWith(prefix) {38 return this.findNode(prefix) !== null;39 }40}41
42const trie = new Trie();43for (const word of ["car", "card", "care", "dog"]) trie.insert(word);44console.log("search(\"card\"):", trie.search("card"));45console.log("search(\"ca\"):", trie.search("ca"));46console.log("startsWith(\"ca\"):", trie.startsWith("ca"));Kode Trie (Prefix Tree) dalam Java
Java
1public class Main {2 static class Node {3 Node[] children = new Node[26];4 boolean isWord;5 }6
7 static Node root = new Node();8
9 static void insert(String word) {10 Node cur = root;11 for (char c : word.toCharArray()) {12 int i = c - 'a';13 if (cur.children[i] == null) cur.children[i] = new Node();14 cur = cur.children[i];15 }16 cur.isWord = true;17 }18
19 // Follow the path for s; null means no word has this prefix20 static Node walk(String s) {21 Node cur = root;22 for (char c : s.toCharArray()) {23 cur = cur.children[c - 'a'];24 if (cur == null) return null;25 }26 return cur;27 }28
29 static boolean search(String word) {30 Node node = walk(word);31 return node != null && node.isWord;32 }33
34 static boolean startsWith(String prefix) {35 return walk(prefix) != null;36 }37
38 public static void main(String[] args) {39 insert("code");40 insert("coder");41 insert("cool");42 System.out.println("search code: " + search("code"));43 System.out.println("search cod: " + search("cod"));44 System.out.println("startsWith cod: " + startsWith("cod"));45 System.out.println("startsWith cat: " + startsWith("cat"));46 }47}Kode Trie (Prefix Tree) dalam C++
C++
1#include <iostream>2#include <string>3#include <unordered_map>4
5struct TrieNode {6 std::unordered_map<char, TrieNode*> children;7 bool isEnd = false;8};9
10struct Trie {11 TrieNode* root = new TrieNode();12
13 void insert(const std::string& word) {14 TrieNode* node = root;15 for (char c : word) {16 if (!node->children.count(c)) node->children[c] = new TrieNode();17 node = node->children[c];18 }19 node->isEnd = true;20 }21
22 // Follow the path for s; nullptr if a link is missing23 TrieNode* walk(const std::string& s) const {24 TrieNode* node = root;25 for (char c : s) {26 auto it = node->children.find(c);27 if (it == node->children.end()) return nullptr;28 node = it->second;29 }30 return node;31 }32
33 bool search(const std::string& word) const {34 TrieNode* node = walk(word);35 return node != nullptr && node->isEnd;36 }37
38 bool startsWith(const std::string& prefix) const {39 return walk(prefix) != nullptr;40 }41};42
43int main() {44 Trie trie;45 for (const std::string& word : {"car", "card", "care", "dog"}) {46 trie.insert(word);47 }48 std::cout << std::boolalpha;49 std::cout << "search(card): " << trie.search("card") << "\n";50 std::cout << "search(ca): " << trie.search("ca") << "\n";51 std::cout << "startsWith(ca): " << trie.startsWith("ca") << "\n";52 std::cout << "startsWith(dot): " << trie.startsWith("dot") << "\n";53 return 0;54}Kode Trie (Prefix Tree) dalam C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct TrieNode {6 struct TrieNode* children[26];7 bool isEnd;8} TrieNode;9
10TrieNode* newNode(void) {11 return calloc(1, sizeof(TrieNode)); // zeroed links and isEnd12}13
14void insert(TrieNode* root, const char* word) {15 for (; *word; word++) {16 int i = *word - 'a';17 if (root->children[i] == NULL) root->children[i] = newNode();18 root = root->children[i];19 }20 root->isEnd = true;21}22
23// Follow the path for s; NULL if a link is missing24TrieNode* walk(TrieNode* root, const char* s) {25 for (; *s; s++) {26 root = root->children[*s - 'a'];27 if (root == NULL) return NULL;28 }29 return root;30}31
32bool search(TrieNode* root, const char* word) {33 TrieNode* node = walk(root, word);34 return node != NULL && node->isEnd;35}36
37bool startsWith(TrieNode* root, const char* prefix) {38 return walk(root, prefix) != NULL;39}40
41int main(void) {42 TrieNode* root = newNode();43 const char* words[] = {"car", "card", "care", "dog"};44 for (int i = 0; i < 4; i++) insert(root, words[i]);45 printf("search(card): %s\n", search(root, "card") ? "true" : "false");46 printf("search(ca): %s\n", search(root, "ca") ? "true" : "false");47 printf("startsWith(ca): %s\n", startsWith(root, "ca") ? "true" : "false");48 printf("startsWith(dot): %s\n", startsWith(root, "dot") ? "true" : "false");49 return 0;50}FAQ Trie
Untuk apa trie dipakai?
Trie menggerakkan fitur berbasis prefiks: autocomplete dan saran pencarian, pemeriksa ejaan, tabel routing IP, dan pencarian kamus. Di mana pun kamu butuh query cepat "adakah kata tersimpan yang diawali prefiks ini?", trie unggul.
Berapa kompleksitas waktu trie?
Penyisipan, pencarian, dan query prefiks semuanya berjalan dalam waktu
O(m), dengan m adalah panjang kata atau prefiksnya, tidak bergantung pada berapa banyak kata yang disimpan. Pertukarannya ada di memori: trie bisa memakan banyak ruang, meskipun prefiks yang sama hanya disimpan sekali.Apa perbedaan trie dan hash table?
Hash table menawarkan pencarian key utuh rata-rata
O(1), tetapi tidak bisa menjawab query prefiks. Trie sedikit lebih lambat per pencarian, tetapi secara alami mendukung pencarian prefiks, penelusuran terurut, dan autocomplete, dan itulah alasan trie lebih dipilih untuk kebutuhan tersebut.Kapan sebaiknya memakai trie, bukan binary search tree?
Pakai trie saat key-mu berupa string dan kamu butuh pencarian prefiks: trie berjalan dalam
O(m) per operasi berdasarkan panjang key, sedangkan BST yang seimbang berbiaya O(m log n) karena setiap perbandingan memindai string dan ada log n perbandingan. BST adalah pilihan yang lebih baik saat key-nya tidak berbentuk string atau saat beban memori lebih penting daripada kecepatan prefiks.Bagaimana cara menangani akhir kata dalam trie?
Setiap node membawa penanda akhir kata yang hanya diaktifkan saat sebuah kata utuh yang disisipkan berakhir di sana. Tanpa penanda itu, kamu tidak bisa membedakan kata yang disimpan dari sekadar prefiks. Contohnya, setelah menyisipkan
card, node untuk car memang ada, tetapi hanya boleh dilaporkan sebagai kata jika car juga disisipkan.Apakah trie selalu menghemat memori dengan berbagi prefiks?
Tidak selalu. Berbagi prefiks hanya membantu jika banyak key yang tumpang tindih; dengan key yang panjang dan berbeda-beda, trie bisa memakai jauh lebih banyak memori daripada hash set, karena setiap karakter menjadi node tersendiri dengan pointer anak. Jika ruang menjadi perhatian, compressed radix tree menggabungkan rantai node yang hanya punya satu anak untuk memangkas beban itu.
Sumber terkait
Visualisasi lainnya
