Trie (prefix tree): cara kerja, kode Python, dan kompleksitasnya

Masalah apa yang diselesaikan trie

Hash set menjawab "apakah kata persis ini tersimpan?" dengan cepat, tetapi tidak bisa menjawab "kata tersimpan mana yang diawali pre?" tanpa memeriksa setiap kata. Sorted list bisa menjawab query prefix dengan binary search, tetapi insert-nya lambat. Trie diorganisasi berdasarkan prefix, jadi pertanyaan prefix adalah kekuatan alaminya: autocomplete di kotak pencarian, game kata, spell checking, dan longest-prefix matching untuk rute jaringan.

Ide dasarnya dengan bahasa sederhana

Bayangkan daftar kontak telepon yang Anda persempit satu huruf demi satu huruf. Mengetik c menampilkan semua yang diawali c, mengetik ca mempersempit daftar, dan seterusnya. Trie menyimpan kata-kata persis dalam bentuk itu. Root adalah prefix kosong. Setiap node punya map dari karakter berikutnya ke node anak, plus flag end-of-word, karena kata seperti car bisa menjadi kata utuh sekaligus prefix dari cart.

Contoh langkah demi langkah: insert car, cart, cat, dan dog

Keempat kata punya total 13 huruf tetapi hanya butuh 8 node di bawah root (c, a, r, t, t, d, o, g), karena car, cart, dan cat berbagi ca. Mencari ca menelusuri dua node dan berhasil sebagai prefix, tetapi ca bukan kata karena node-nya tidak ditandai sebagai akhir. Mencari cow gagal pada langkah kedua: node c tidak punya anak o.

Implementasi Python

Setiap node menyimpan dict berisi anak-anaknya, yang menangani alfabet apa pun termasuk Unicode. Method starts_with mengumpulkan setiap kata di bawah sebuah prefix, inti dari autocomplete.

class TrieNode:
    __slots__ = ("children", "is_word")
    def __init__(self):
        self.children = {}
        self.is_word = False
class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True
    def _find(self, prefix):
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node
    def contains(self, word):
        node = self._find(word)
        return node is not None and node.is_word
    def starts_with(self, prefix):
        node, out = self._find(prefix), []
        stack = [(node, prefix)] if node else []
        while stack:
            node, path = stack.pop()
            if node.is_word:
                out.append(path)
            for ch, child in node.children.items():
                stack.append((child, path + ch))
        return sorted(out)

t = Trie()
for w in ["car", "cart", "cat", "dog"]:
    t.insert(w)
print(t.contains("car"), t.contains("ca"))  # True False
print(t.starts_with("ca"))                  # ['car', 'cart', 'cat']
print(t.starts_with("x"))                   # []

starts_with mengurutkan outputnya agar urutannya stabil. Autocomplete yang sebenarnya juga akan berhenti setelah beberapa hasil pertama dan meranking-nya, misalnya berdasarkan hitungan popularitas yang tersimpan.

Kompleksitas waktu dan ruang

Waktunya tidak bergantung pada jumlah kata n, yang merupakan keunggulan utama dibanding balanced tree berisi string (O(m log n) perbandingan). Harganya adalah memori: setiap node adalah objek terpisah dengan dictionary-nya sendiri, sehingga trie bisa memakai memori beberapa kali lipat dibanding string mentahnya.

Varian dan kesalahan umum

• Anak berbentuk array: pakai array tetap berisi 26 slot untuk huruf kecil bahasa Inggris. Lebih cepat dari dict, tetapi boros untuk alfabet yang jarang terisi atau besar.
• Compressed trie (radix tree, Patricia trie): menggabungkan rantai node beranak tunggal menjadi satu edge berlabel string, yang menghemat banyak memori. Radix tree dipakai pada tabel routing IP dan di beberapa HTTP router.
• Ternary search tree: setiap node punya tiga anak (kurang, sama, lebih), yang memakai lebih sedikit memori daripada array lebar.
• Counting trie: simpan counter di setiap node untuk menjawab "berapa banyak kata yang diawali prefix ini?" dalam O(m).
• Bitwise trie: simpan angka bit demi bit untuk menyelesaikan soal maximum-XOR.

Kapan memakai trie dan soal wawancara yang khas

Gunakan trie ketika Anda butuh query prefix, longest-prefix matching, atau iterasi terurut atas banyak string yang berbagi prefix. Gunakan set atau dict jika Anda hanya butuh lookup persis: lebih sederhana dan lebih hemat memori di Python. Untuk daftar kata yang kecil dan statis, sorted list dengan modul bisect juga menjawab query prefix dengan baik.

Soal khas: mengimplementasikan trie (insert, search, starts-with), word search di grid dengan banyak kata target, mengganti kata dengan root terpendeknya, longest common prefix, merancang sistem autocomplete pencarian, dan maximum XOR dua angka memakai bitwise trie.