KamusNgoding
Mahir Data-structures 5 menit baca

Panduan Lengkap Implementasi Tries (Prefix Tree)

#trie #prefix tree #data structure #advanced #autocomplete
📚

Baca dulu sebelum ini:

Panduan Lengkap Implementasi Tries (Prefix Tree)

Pendahuluan

Bayangkan kamu sedang membangun fitur autocomplete untuk aplikasi pencarian seperti yang ada di Tokopedia atau Shopee — saat pengguna mengetik “sepa”, sistem langsung menyarankan “sepatu”, “sepatu lari”, “sepatu boots”. Bagaimana cara mereka melakukannya dengan sangat cepat?

Jawabannya adalah Trie (dibaca “try”), juga dikenal sebagai Prefix Tree atau Digital Tree. Trie adalah struktur data berbasis pohon yang dioptimalkan khusus untuk operasi berbasis string, terutama pencarian berdasarkan awalan (prefix). Berbeda dengan struktur data lain seperti Hash Table yang telah kita bahas, Trie menyimpan karakter per karakter dan memanfaatkan kesamaan awalan antar string untuk efisiensi memori dan kecepatan pencarian.

Artikel ini membahas implementasi Trie dari nol menggunakan Python, termasuk operasi lanjutan seperti delete dan autocomplete. Pemahaman dasar tentang OOP di Python: Class, Object, dan Inheritance sangat membantu sebelum melanjutkan.

Konsep Dasar dan Struktur Tries

Apa Itu Node dalam Trie?

Trie terdiri dari node-node yang masing-masing merepresentasikan satu karakter. Setiap node memiliki:

  • children: dictionary yang memetakan karakter ke node anak
  • is_end_of_word: boolean yang menandai apakah node ini merupakan akhir dari sebuah kata valid

Contoh visual untuk kata “api”, “apel”, “apa”:

root
 └── 'a'
      └── 'p'
           ├── 'i' (is_end=True)   → "api"
           ├── 'e'
           │    └── 'l' (is_end=True) → "apel"
           └── 'a' (is_end=True)   → "apa"

Perhatikan bagaimana awalan “ap” hanya disimpan sekali, meski digunakan oleh tiga kata. Inilah keunggulan utama Trie dibanding menyimpan string secara terpisah di array.

Kompleksitas Waktu

OperasiTrieHash Table
InsertO(m)O(m) average
SearchO(m)O(m) average
Prefix SearchO(m + k)O(n·m)
DeleteO(m)O(m)

di mana m = panjang kata, k = jumlah hasil prefix, n = total kata.

Untuk operasi prefix search, Trie jauh lebih unggul — sesuatu yang tidak bisa dilakukan Hash Table secara efisien tanpa iterasi penuh. Memahami notasi kompleksitas ini penting; kamu bisa pelajari lebih lanjut di Mengenal Big O Notation: Cara Mengukur Efisiensi Algoritma.

Implementasi Tries dari Awal di Python

Mendefinisikan TrieNode dan Kelas Trie

Kita mulai dengan mendefinisikan TrieNode sebagai blok bangunan dasar, lalu membangun kelas Trie dengan tiga operasi inti: insert, search, dan starts_with.

class TrieNode:
    def __init__(self):
        # Menyimpan pasangan karakter -> node anak
        self.children: dict[str, "TrieNode"] = {}
        # Menandai apakah node ini adalah akhir dari sebuah kata valid
        self.is_end_of_word: bool = False


class Trie:
    def __init__(self):
        # Root tidak menyimpan karakter; hanya titik awal traversal
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """Menyisipkan kata ke dalam Trie. Kompleksitas: O(m)"""
        current = self.root
        for char in word:
            # Buat node baru hanya jika jalur karakter belum ada
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]
        # Tandai bahwa jalur ini merepresentasikan kata lengkap
        current.is_end_of_word = True

    def search(self, word: str) -> bool:
        """Mencari kata lengkap di Trie. Kompleksitas: O(m)"""
        current = self.root
        for char in word:
            # Jika satu karakter tidak ditemukan, kata pasti tidak ada
            if char not in current.children:
                return False
            current = current.children[char]
        # Harus berakhir tepat di node akhir kata
        return current.is_end_of_word

    def starts_with(self, prefix: str) -> bool:
        """Mengecek apakah ada kata dengan awalan tertentu. Kompleksitas: O(m)"""
        current = self.root
        for char in prefix:
            # Prefix gagal jika jalurnya terputus
            if char not in current.children:
                return False
            current = current.children[char]
        return True


if __name__ == "__main__":
    trie = Trie()

    # Menyisipkan beberapa kata ke dalam Trie
    for word in ["api", "apel", "apa", "apakah", "buku", "bulan"]:
        trie.insert(word)

    # Pengujian pencarian kata lengkap
    print(trie.search("apel"))      # True
    print(trie.search("apelu"))     # False
    print(trie.search("api"))       # True

    # Pengujian prefix
    print(trie.starts_with("ap"))   # True
    print(trie.starts_with("bum"))  # False

Output:

True
False
True
True
False

Operasi Lanjutan: Delete dan Autocomplete

Delete (Hapus Kata)

Menghapus kata dari Trie lebih kompleks karena kita harus mempertimbangkan apakah node yang akan dihapus masih digunakan kata lain. Strategi yang digunakan adalah rekursi dengan pruning — node hanya dihapus jika tidak punya anak dan bukan akhir kata lain.

class TrieNode:
    def __init__(self) -> None:
        self.children: dict[str, "TrieNode"] = {}
        self.is_end_of_word: bool = False


class Trie:
    def __init__(self) -> None:
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            node = node.children.setdefault(char, TrieNode())
        node.is_end_of_word = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def starts_with(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

    def delete(self, word: str) -> bool:
        """
        Menghapus kata dari Trie.
        Mengembalikan True jika berhasil, False jika kata tidak ditemukan.
        """

        def _delete_recursive(node: TrieNode, depth: int) -> tuple[bool, bool]:
            # Basis rekursi: seluruh karakter sudah diproses
            if depth == len(word):
                # Jika node bukan akhir kata, berarti kata tidak ada
                if not node.is_end_of_word:
                    return False, False
                # Hapus penanda akhir kata
                node.is_end_of_word = False
                # Node boleh dipangkas jika tidak punya anak
                return True, len(node.children) == 0

            char = word[depth]
            child = node.children.get(char)

            # Jalur karakter tidak ada, berarti kata tidak ditemukan
            if child is None:
                return False, False

            deleted, should_prune_child = _delete_recursive(child, depth + 1)

            # Jika child tidak lagi dibutuhkan, hapus dari children
            if should_prune_child:
                del node.children[char]

            # Node saat ini boleh dipangkas jika:
            # 1) bukan akhir kata lain, dan
            # 2) tidak punya anak lagi
            should_prune_current = not node.is_end_of_word and len(node.children) == 0
            return deleted, should_prune_current

        deleted, _ = _delete_recursive(self.root, 0)
        return deleted


if __name__ == "__main__":
    trie = Trie()

    # Masukkan beberapa kata yang berbagi prefix "ap"
    for word in ["api", "apel", "apa"]:
        trie.insert(word)

    # Hapus hanya kata "apel" tanpa merusak cabang kata lain
    print(trie.delete("apel"))      # True
    print(trie.search("apel"))      # False — sudah dihapus
    print(trie.search("api"))       # True — masih ada
    print(trie.starts_with("ap"))   # True — prefix masih valid

    # Coba hapus kata yang tidak ada
    print(trie.delete("apelu"))     # False

    # Contoh lain: kata berbagi prefix panjang
    trie2 = Trie()
    for word in ["cat", "car", "care"]:
        trie2.insert(word)

    print(trie2.delete("car"))      # True
    print(trie2.search("car"))      # False
    print(trie2.search("care"))     # True — node "care" tetap ada
    print(trie2.delete("dog"))      # False — tidak ditemukan

Output:

True
False
True
True
False
True
False
True
False

Autocomplete

Ini adalah operasi paling berguna dari Trie — menemukan semua kata dengan awalan tertentu menggunakan DFS (Depth-First Search).

from __future__ import annotations


class TrieNode:
    def __init__(self) -> None:
        self.children: dict[str, TrieNode] = {}
        self.is_end_of_word: bool = False


class Trie:
    def __init__(self) -> None:
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        current = self.root
        for char in word:
            current = current.children.setdefault(char, TrieNode())
        current.is_end_of_word = True

    def autocomplete(self, prefix: str) -> list[str]:
        """
        Mengembalikan semua kata yang dimulai dengan prefix tertentu.
        Kompleksitas: O(m + k)
        m = panjang prefix, k = total karakter dari semua hasil
        """
        current = self.root

        # Navigasi ke node akhir dari prefix
        for char in prefix:
            if char not in current.children:
                return []  # Prefix tidak ditemukan di trie
            current = current.children[char]

        results: list[str] = []

        def dfs(node: TrieNode, path: list[str]) -> None:
            # Jika node menandai akhir kata, simpan hasil lengkap
            if node.is_end_of_word:
                results.append(prefix + "".join(path))

            # Urutkan anak agar output konsisten dan deterministik
            for char in sorted(node.children):
                path.append(char)
                dfs(node.children[char], path)
                path.pop()  # Backtrack setelah rekursi selesai

        dfs(current, [])
        return results


if __name__ == "__main__":
    trie = Trie()
    kata_kata = [
        "python", "pytorch", "pyenv",
        "pandas", "panel",
        "numpy", "notebook"
    ]

    for kata in kata_kata:
        trie.insert(kata)

    print(trie.autocomplete("py"))   # Semua kata berawalan "py"
    print(trie.autocomplete("pan"))  # Semua kata berawalan "pan"
    print(trie.autocomplete("no"))   # Semua kata berawalan "no"
    print(trie.autocomplete("xyz"))  # Prefix tidak ada

Output:

['pyenv', 'python', 'pytorch']
['pandas', 'panel']
['notebook']
[]

Catatan: Urutan hasil terurut secara alfabetis karena kita menelusuri sorted(node.children) di setiap langkah DFS. “python” muncul sebelum “pytorch” karena ‘h’ < ‘o’ pada posisi ke-4.

Autocomplete dengan Limit

Untuk aplikasi produksi, kita perlu membatasi jumlah hasil agar tidak membebani sistem:

from __future__ import annotations


class TrieNode:
    def __init__(self) -> None:
        self.children: dict[str, TrieNode] = {}
        self.is_end_of_word: bool = False


class Trie:
    def __init__(self) -> None:
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        current = self.root
        for char in word:
            current = current.children.setdefault(char, TrieNode())
        current.is_end_of_word = True

    def autocomplete(self, prefix: str) -> list[str]:
        """Autocomplete tanpa batas."""
        return self.autocomplete_limited(prefix, limit=0)

    def autocomplete_limited(self, prefix: str, limit: int = 10) -> list[str]:
        """
        Autocomplete dengan batas maksimum hasil.
        limit=0 berarti tidak ada batas (kembalikan semua).
        """
        current = self.root

        for char in prefix:
            if char not in current.children:
                return []
            current = current.children[char]

        results: list[str] = []

        def _collect(node: TrieNode, path: list[str]) -> None:
            # Hentikan DFS segera saat batas hasil tercapai
            if limit > 0 and len(results) >= limit:
                return

            if node.is_end_of_word:
                results.append(prefix + "".join(path))

            for char in sorted(node.children):
                if limit > 0 and len(results) >= limit:
                    return
                path.append(char)
                _collect(node.children[char], path)
                path.pop()

        _collect(current, [])
        return results


if __name__ == "__main__":
    trie = Trie()
    words = [
        "app", "apple", "application", "apply", "apt",
        "banana", "band", "bandwidth", "bandung", "banner",
    ]

    for word in words:
        trie.insert(word)

    # Tanpa limit
    print(trie.autocomplete("app"))
    # Dengan limit 3
    print(trie.autocomplete_limited("app", limit=3))
    # Semua kata berawalan "ban"
    print(trie.autocomplete("ban"))
    # Hanya 2 hasil pertama
    print(trie.autocomplete_limited("ban", limit=2))

Output:

['app', 'apple', 'application', 'apply', 'apt']
['app', 'apple', 'application']
['banana', 'band', 'bandung', 'bandwidth', 'banner']
['banana', 'band']

Contoh Kasus Nyata

Kasus 1: Spell Checker Sederhana

Jika ingin membangun fitur spell checker seperti yang ada di editor kode, kita bisa menggunakan Trie sebagai kamus internal:

class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end_of_word: bool = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            node = node.children.setdefault(char, TrieNode())
        node.is_end_of_word = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def autocomplete(self, prefix: str) -> list[str]:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]

        results: list[str] = []

        def dfs(current: TrieNode, path: list[str]) -> None:
            if current.is_end_of_word:
                results.append(prefix + "".join(path))
            for char in sorted(current.children):
                path.append(char)
                dfs(current.children[char], path)
                path.pop()

        dfs(node, [])
        return results


class SpellChecker:
    def __init__(self, dictionary: list[str]):
        self.trie = Trie()
        for word in dictionary:
            self.trie.insert(word.lower())

    def is_correct(self, word: str) -> bool:
        return self.trie.search(word.lower())

    def suggest(self, word: str) -> list[str]:
        # Gunakan maksimal 3 karakter pertama sebagai prefix pencarian
        prefix = word[:3].lower()
        return self.trie.autocomplete(prefix)[:5]


if __name__ == "__main__":
    kamus = ["belajar", "beli", "belanja", "belanda", "beta", "bayar"]
    checker = SpellChecker(kamus)

    print(checker.is_correct("beli"))       # True
    print(checker.is_correct("belio"))      # False
    print(checker.suggest("bel"))           # Saran kata berawalan "bel"
    print(checker.suggest("bay"))           # Saran kata berawalan "bay"

Output:

True
False
['belanda', 'belajar', 'belanja', 'beli']
['bayar']

Kasus 2: IP Routing Table

Trie tidak hanya untuk teks. Router jaringan menggunakan prefix tree untuk mencocokkan IP address dengan teknik longest-prefix match:

from __future__ import annotations


class TrieNode:
    def __init__(self) -> None:
        self.children: dict[str, TrieNode] = {}
        self.interface: str | None = None  # Interface jika node ini adalah akhir prefix


class IPRoutingTable:
    """
    Trie sederhana untuk simulasi longest-prefix match pada routing IP.
    Prefix disimpan per oktet, mis. "192.168.1".
    """

    def __init__(self) -> None:
        self.root = TrieNode()

    def add_route(self, ip_prefix: str, interface: str) -> None:
        node = self.root
        for part in ip_prefix.split("."):
            node = node.children.setdefault(part, TrieNode())
        node.interface = interface

    def lookup(self, ip: str) -> str | None:
        node = self.root
        last_match = node.interface

        for part in ip.split("."):
            if part not in node.children:
                break
            node = node.children[part]
            if node.interface is not None:
                last_match = node.interface  # Update kecocokan terpanjang

        return last_match


if __name__ == "__main__":
    router = IPRoutingTable()
    router.add_route("192.168", "eth0")
    router.add_route("192.168.1", "eth1")
    router.add_route("10", "eth2")

    print(router.lookup("192.168.1.100"))   # eth1 (longest prefix match)
    print(router.lookup("192.168.2.50"))    # eth0 (hanya cocok hingga "192.168")
    print(router.lookup("10.0.0.1"))        # eth2
    print(router.lookup("172.16.0.1"))      # None (tidak ada route yang cocok)

Output:

eth1
eth0
eth2
None

Pertanyaan yang Sering Diajukan

Apa perbedaan Trie dengan Binary Search Tree untuk pencarian string?

Binary Search Tree menyimpan string utuh di setiap node dan melakukan perbandingan string secara keseluruhan, dengan kompleksitas O(m log n) untuk pencarian. Trie menyimpan karakter per karakter dan memanfaatkan awalan bersama, sehingga pencarian hanya O(m) tanpa bergantung pada jumlah total kata. Untuk operasi berbasis prefix, Trie tidak ada tandingannya.

Mengapa Trie menggunakan lebih banyak memori dibanding Hash Table?

Setiap karakter dalam Trie membutuhkan satu node dengan children dictionary. Untuk kosakata besar dengan banyak variasi awalan, jumlah node bisa sangat besar. Solusinya adalah menggunakan compressed Trie (Patricia Tree) yang menggabungkan node dengan satu anak, atau menyimpan children sebagai array 26 elemen untuk alfabet Latin alih-alih dictionary.

Bagaimana cara mengoptimalkan Trie untuk data besar?

Beberapa teknik optimasi umum: (1) Compressed Trie — gabungkan node linear menjadi satu edge berlabel string; (2) Array children — ganti dict dengan list[26] untuk alfabet Latin, akses lebih cepat; (3) Serialisasi — simpan Trie ke disk menggunakan BFS order untuk load cepat saat startup; (4) Pruning — batasi kedalaman Trie sesuai panjang maksimum kata yang relevan.

Kapan sebaiknya tidak menggunakan Trie?

Trie kurang tepat ketika: dataset string-nya kecil (overhead memori tidak sebanding), operasi yang dibutuhkan hanya exact match tanpa prefix (Hash Table lebih efisien), atau karakternya non-ASCII dengan jumlah karakter unik yang sangat besar seperti karakter CJK, karena ukuran children per node akan membengkak.

Apa itu Ternary Search Trie dan kapan digunakan?

Ternary Search Trie (TST) adalah varian yang menggabungkan sifat BST dan Trie. Setiap node hanya memiliki tiga anak: left (karakter lebih kecil), equal (karakter sama), dan right (karakter lebih besar). TST lebih hemat memori dari Trie biasa namun tetap mendukung prefix search. Cocok untuk kosakata dengan distribusi karakter tidak merata.

Kesimpulan

Trie adalah struktur data yang sangat powerful untuk masalah berbasis string. Dengan menyimpan karakter per karakter dan berbagi awalan antar kata, Trie memberikan:

  • Pencarian dalam O(m) — konstan terhadap jumlah kata
  • Prefix search dan autocomplete yang tidak bisa dilakukan Hash Table secara efisien
  • Fondasi untuk fitur seperti spell checker, search suggestion, dan IP routing

Kunci implementasi yang baik adalah memahami kapan harus menghapus node saat operasi delete (hanya jika tidak ada anak dan bukan akhir kata lain), dan bagaimana DFS digunakan untuk mengumpulkan semua kata saat autocomplete.

Jika ingin membangun sistem pencarian seperti yang ada di platform e-commerce besar, Trie adalah komponen pertama yang perlu dikuasai sebelum beralih ke solusi lebih kompleks seperti Elasticsearch. Untuk memahami lebih lanjut bagaimana algoritma traversal bekerja di struktur pohon, referensi ke BST dan AVL Tree akan sangat melengkapi pemahaman kamu tentang tree-based data structures.

Artikel Terkait

go Panduan Lengkap Manajemen Error di Go algorithms Implementasi Algoritma Dijkstra: Mencari Rute Terpendek dalam Graf data-structures Apa itu Hash Table? Penjelasan Lengkap untuk Pemula