Trie (dibaca “try”, dari retrieval) adalah tree khusus untuk menyimpan himpunan string dengan prefix sharing. Setiap node merepresentasikan satu karakter, dan path dari root ke node manapun merepresentasikan sebuah prefix. Trie menjawab pertanyaan yang sulit dijawab BST atau hash table: “apakah ada kata dengan prefix app?” atau “apa saja kata yang dimulai dengan app?” dengan efisien. Aplikasi praktisnya luas: autocomplete di Google Search, koreksi ejaan, IP routing table (longest prefix match), dan kamus T9 di ponsel lama. Pada Chapter ini kita akan mengimplementasikan trie dengan operasi insert, search, dan startsWith, menganalisis trade-off memori, dan melihat variasi optimasi (compressed trie / radix trie).

Struktur Trie #

Setiap node trie berisi:

  1. Pointer ke anak-anak per karakter (biasanya array berukuran alphabet size atau std::unordered_map).
  2. Flag is_end menandakan bahwa node ini adalah akhir dari sebuah kata yang disimpan.

Pada diagram di atas, trie menyimpan kata aa, app, apple, bat. Path root → a → p → p berakhir di node yang menandai akhir kata app. Node yang sama adalah ancestor dari apple. Inilah prefix sharing: kata app dan apple berbagi prefix app.

Implementasi Dasar #

cpp 
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

class Trie {
public:
    Trie() : root_(new TrieNode()) {}
    ~Trie() { destroy(root_); }

    void insert(const std::string& word) {
        TrieNode* cur = root_;
        for (char c : word) {
            if (cur->children.find(c) == cur->children.end()) {
                cur->children[c] = new TrieNode();
            }
            cur = cur->children[c];
        }
        cur->is_end = true;
    }

    bool search(const std::string& word) const {
        const TrieNode* node = find_node(word);
        return node != nullptr && node->is_end;
    }

    bool starts_with(const std::string& prefix) const {
        return find_node(prefix) != nullptr;
    }

private:
    struct TrieNode {
        std::unordered_map<char, TrieNode*> children;
        bool is_end = false;
    };

    TrieNode* root_;

    const TrieNode* find_node(const std::string& s) const {
        const TrieNode* cur = root_;
        for (char c : s) {
            auto it = cur->children.find(c);
            if (it == cur->children.end()) return nullptr;
            cur = it->second;
        }
        return cur;
    }

    void destroy(TrieNode* node) {
        for (auto& kv : node->children) destroy(kv.second);
        delete node;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("app");
    trie.insert("bat");
    trie.insert("ba");

    std::cout << "search(\"apple\") : " << (trie.search("apple") ? "ya" : "tidak") << '\n';
    std::cout << "search(\"app\")   : " << (trie.search("app")   ? "ya" : "tidak") << '\n';
    std::cout << "search(\"appl\")   : " << (trie.search("appl")  ? "ya" : "tidak") << '\n';
    std::cout << "search(\"bat\")    : " << (trie.search("bat")   ? "ya" : "tidak") << '\n';
    std::cout << "search(\"cat\")    : " << (trie.search("cat")   ? "ya" : "tidak") << '\n';

    std::cout << '\n';
    std::cout << "starts_with(\"app\") : " << (trie.starts_with("app") ? "ya" : "tidak") << '\n';
    std::cout << "starts_with(\"ba\")  : " << (trie.starts_with("ba")  ? "ya" : "tidak") << '\n';
    std::cout << "starts_with(\"ca\")  : " << (trie.starts_with("ca")  ? "ya" : "tidak") << '\n';
    std::cout << "starts_with(\"bats\"): " << (trie.starts_with("bats")? "ya" : "tidak") << '\n';

    return 0;
}

Output yang Dihasilkan:

text 
search("apple") : ya
search("app")   : ya
search("appl")   : tidak
search("bat")    : ya
search("cat")    : tidak

starts_with("app") : ya
starts_with("ba")  : ya
starts_with("ca")  : tidak
starts_with("bats"): tidak
  1. Struct TrieNode: pakai std::unordered_map<char, TrieNode*> untuk children. Untuk alphabet kecil (mis. huruf kecil a-z), array TrieNode*[26] lebih cepat dan hemat overhead per node. Map fleksibel untuk Unicode atau alphabet besar.
  2. insert: traverse per karakter. Bila child belum ada, buat node baru. Setelah loop, set is_end = true untuk menandai akhir kata.
  3. search: traverse per karakter. Bila child tidak ada → kata tidak tersimpan. Bila traverse selesai → cek is_end. Pencarian “appl” gagal karena tidak ada node is_end setelah path a-p-p-l (leaf tidak punya is_end).
  4. starts_with: hanya traverse, tidak peduli is_end. Cukup cek apakah path prefix ada.
  5. search("app") = ya tapi search("appl") = tidak: kata app disimpan sebagai path root→a→p→p dengan is_end=true. Kata appl tidak disimpan; meskipun path ada (sebagai prefix dari apple), is_end tidak diset.

Kompleksitas Trie #

OperasiWaktuCatatan
Insert kata s panjang mO(m)Traverse m karakter
Search kata sO(m)Sama dengan insert
starts_with prefix pO(p)Hanya traverse prefix
Prefix search (semua kata mulai p)O(p + jumlah hasil)BFS/DFS dari node prefix
MemoriO(total karakter semua kata)Sering lebih besar dari hash table

Trie tidak bergantung pada jumlah kata (n) — hanya pada panjang kata (m). Untuk kata panjang rata-rata 10 karakter, insert/search 10 langkah terlepas dari jumlah kata dalam kamus 1 juta. Hash table juga O(m) average untuk hash, namun trie unggul pada prefix query.

Autocomplete dengan Trie #

Salah satu aplikasi paling natural trie: ambil semua kata yang dimulai dengan prefix tertentu.

cpp 
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

class AutocompleteTrie {
public:
    void insert(const std::string& word) {
        Node* cur = &root_;
        for (char c : word) {
            auto it = cur->children.find(c);
            if (it == cur->children.end()) {
                cur->children[c] = Node{};
            }
            cur = &cur->children[c];
        }
        cur->is_end = true;
    }

    std::vector<std::string> suggest(const std::string& prefix) const {
        const Node* cur = &root_;
        std::string path;
        for (char c : prefix) {
            auto it = cur->children.find(c);
            if (it == cur->children.end()) return {};
            cur = &it->second;
            path.push_back(c);
        }
        std::vector<std::string> results;
        dfs(cur, path, results);
        return results;
    }

private:
    struct Node {
        std::unordered_map<char, Node> children;
        bool is_end = false;
    };

    Node root_;

    void dfs(const Node* node, std::string& path, std::vector<std::string>& out) const {
        if (node->is_end) out.push_back(path);
        for (const auto& kv : node->children) {
            path.push_back(kv.first);
            dfs(&kv.second, path, out);
            path.pop_back();
        }
    }
};

int main() {
    AutocompleteTrie trie;
    for (const std::string& w : {
        "applause", "apple", "application", "apply", "appoint", "banana", "band"
    }) {
        trie.insert(w);
    }

    for (const std::string& prefix : {"app", "ban", "xyz"}) {
        std::cout << "Suggest(\"" << prefix << "\"): ";
        auto results = trie.suggest(prefix);
        for (const auto& s : results) std::cout << s << ' ';
        std::cout << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
Suggest("app"): appoint apply application apple applause 
Suggest("ban"): band banana 
Suggest("xyz"):
  1. Node pakai std::unordered_map<char, Node> (in-place): tidak perlu pointer alokasi dinamis. Node disimpan di dalam map sebagai value. Lebih sederhana, namun tidak bisa di-copy dengan mudah.
  2. suggest: pertama traverse prefix untuk menemukan node tujuan. Bila tidak ada → return kosong. Bila ada → DFS untuk kumpulkan semua kata yang ada is_end = true di subtree.
  3. DFS backtrack: dorong karakter ke path sebelum rekursi, pop setelahnya — pola backtracking klasik.
  4. Hasil Suggest("app"): 5 kata mulai dengan app. Output urutannya bergantung iterasi unordered_map (non-deterministik antar compiler, tetapi konsisten dalam satu run).

Variasi dan Optimasi Trie #

VariasiKarakteristikCocok untuk
Standard trieNode per karakterPencarian umum
Compressed trie (radix)Edge berisi substringHemat memori (IP routing)
Suffix trieSemua suffix dari satu stringPattern matching, bioinformatika
Ternary search treeBST per node dengan 3 anakHemat memori, dictionary spell-checker

Ringkasan #

  • Trie adalah tree khusus untuk string: setiap node = satu karakter, path root→node = prefix.
  • Tiga operasi dasar: insert (O(m)), search (O(m)), starts_with (O(m)) — m adalah panjang kata/prefix, tidak bergantung jumlah kata dalam trie.
  • Prefix sharing menjadikan trie efisien untuk autocomplete dan prefix query — operasi yang sulit di hash table atau BST.
  • Trade-off: memori besar (setiap karakter punya node sendiri). Compressed trie menggabungkan edge berderajat 1 untuk mengurangi memori.
  • Aplikasi nyata: autocomplete search engine, spell-checker, IP routing (longest prefix match), T9 dictionary, DNA sequence matching (suffix trie).