Trie — Autocomplete, IP routing, và prefix-friendly dictionary

Bạn cần build autocomplete cho 1 triệu tên sản phẩm. Người dùng gõ "ca", hệ thống phải trả về mọi từ bắt đầu bằng "ca" trong vòng vài millisecond.

Với HashMap: không thể tìm prefix — bạn phải scan toàn bộ 1 triệu key, kiểm tra từng cái xem có bắt đầu bằng "ca" không — O(n × L), tệ. Với TreeMap (Red-Black tree): có thể dùng subMap("ca", "cb") để lấy prefix range — nhưng mỗi lần so sánh key vẫn phải compare full string, và kết quả vẫn phải traverse nhiều node trên tree.

Câu trả lời là Trie (đọc như "try") — cây mà mỗi node đại diện cho một ký tự, và mỗi path từ root đến leaf là một từ hoàn chỉnh. Tìm prefix = đi theo path ký tự — O(L) với L là độ dài prefix, hoàn toàn độc lập với n (số từ đã lưu).

Bài này dạy trie cơ bản, variant nén (Patricia/Radix tree), các use case thực tế (autocomplete, IP routing, dictionary), và trade-off memory vs lookup speed.

1. Analogy — Bản đồ chữ

Hình dung một mê cung với các ngã rẽ được dán nhãn chữ cái. Từ điểm xuất phát (root), bạn đi theo từng ký tự của từ cần tìm: muốn tìm "car", rẽ theo "c" → "a" → "r". Đến nơi, bạn đã tìm thấy "car".

Điều đặc biệt: tất cả từ bắt đầu bằng "ca" đều đi qua cùng một ngã rẽ "c" rồi "a". Muốn liệt kê tất cả từ bắt đầu bằng "ca"? Đi đến giao lộ "ca", rồi khám phá tất cả nhánh con từ đó: rẽ "r" ra "car", rẽ "t" ra "cat", rẽ "n" ra "can". Không cần quét toàn bộ dictionary.

2. Cấu trúc trie cơ bản

Mỗi node trong trie cần hai thứ: map từ ký tự sang node con, và flag đánh dấu node này có phải điểm kết thúc từ không.

class TrieNode {
    // Map from character to child node.
    // Alternative: TrieNode[26] for a-z only (faster but wastes memory).
    Map<Character, TrieNode> children = new HashMap<>();

    // True if this node marks the end of a valid word.
    boolean isEnd;
}

class Trie {
    private final TrieNode root = new TrieNode();
}

Trade-off Map<Character, TrieNode> vs TrieNode[26]:

Với Java 21, HashMap là lựa chọn mặc định an toàn cho ASCII alphabet. Với Unicode (65k+ character), TrieNode[65536] sẽ tốn khoảng 256KB mỗi node — hoàn toàn không khả thi.

3. Insert, Search, và startsWith

public void insert(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        // Create child node if it does not exist yet.
        node = node.children.computeIfAbsent(c, k -> new TrieNode());
    }
    node.isEnd = true;  // mark end of word
}

public boolean search(String word) {
    TrieNode node = walk(word);
    // Must reach a node AND that node must be a word-end.
    return node != null && node.isEnd;
}

public boolean startsWith(String prefix) {
    // Only need to reach the prefix node -- no isEnd check needed.
    return walk(prefix) != null;
}

// Walk down the trie following each character of s.
// Returns the node reached, or null if path does not exist.
private TrieNode walk(String s) {
    TrieNode node = root;
    for (char c : s.toCharArray()) {
        node = node.children.get(c);
        if (node == null) return null;
    }
    return node;
}

ASCII diagram — trie sau khi insert ["car", "cart", "cat", "can", "dog"]:

root
├── c
│   └── a
│       ├── r  [isEnd=true]  ("car")
│       │   └── t  [isEnd=true]  ("cart")
│       ├── t  [isEnd=true]  ("cat")
│       └── n  [isEnd=true]  ("can")
└── d
    └── o
        └── g  [isEnd=true]  ("dog")

Node "c" và "a" được chia sẻ bởi "car", "cart", "cat", "can". Đây chính là lợi thế memory của trie — prefix chung không bị lưu nhiều lần.

4. Độ phức tạp

Điểm quan trọng nhất: time complexity hoàn toàn độc lập với n (số từ đã insert). Dù trie có 10 hay 10 triệu từ, search "cart" luôn chỉ đi qua đúng 4 node. Đây là điểm mà HashMap và TreeMap không sánh được cho prefix query.

Memory cost: worst case O(N × L) với N là số từ và L là độ dài trung bình — khi không có prefix nào chung. Với từ điển thực tế (nhiều prefix chung), memory tiết kiệm hơn đáng kể. Trường hợp nhiều từ ngắn distinct là tệ nhất cho trie.

5. Memory optimization — Patricia / Radix tree

Trie cơ bản có điểm yếu: chuỗi node đơn con (single-child chain) lãng phí. Hãy xem trie của ["interest", "interesting", "internal"]:

root
└── i
    └── n
        └── t
            └── e
                └── r  <-- chain khong co nhanh: i-n-t-e-r
                    ├── e
                    │   └── s
                    │       └── t  [isEnd=true]  ("interest")
                    │           └── i
                    │               └── n
                    │                   └── g  [isEnd=true]  ("interesting")
                    └── n
                        └── a
                            └── l  [isEnd=true]  ("internal")

Chain i→n→t→e→r không có nhánh nào — 5 node chỉ để lưu prefix "inter". Patricia tree (còn gọi là Radix tree) nén chain này thành một edge duy nhất có label "inter":

root
└── "inter"
    ├── "est"  [isEnd=true]  ("interest")
    │   └── "ing"  [isEnd=true]  ("interesting")
    └── "nal"  [isEnd=true]  ("internal")

Thay vì 14 node, chỉ cần 5 node + edge labels. Lookup vẫn O(L) nhưng phức tạp hơn: khi đi theo một edge, phải match prefix của search string với edge label, xử lý trường hợp match một phần (partial match) để biết rẽ tiếp hay dừng.

Patricia/Radix tree được dùng bởi:

• Linux kernel IP routing table — longest prefix match cho IPv4/IPv6
• Git pack-refs index
• Ethereum state trie (Patricia Merkle tree)
• Nhiều router firmware cho routing table

6. Bài kinh điển — Top-K Autocomplete

Khi build search box, không chỉ cần prefix match mà còn cần trả về K từ phổ biến nhất theo prefix.

Approach 1 — Pre-computed top-K per node (LeetCode 642):

Mỗi node lưu sẵn list K từ phổ biến nhất trong subtree của nó. Khi insert từ với frequency, cập nhật list top-K từ root xuống đến node cuối cùng.

class AutocompleteNode {
    Map<Character, AutocompleteNode> children = new HashMap<>();
    boolean isEnd;
    // Top-K words reachable from this node, sorted by frequency desc.
    List<String> topK = new ArrayList<>();
}

• Lookup: O(L) — walk xuống prefix node, trả về node.topK ngay lập tức.
• Insert: O(L × K) — cập nhật top-K tại mỗi node trên path (L node, mỗi node sort K element).
• Trade-off: query nhanh, nhưng insert chậm hơn và tốn memory (mỗi node lưu K chuỗi).

Approach 2 — Lazy DFS + heap:

Chỉ lưu frequency tại node lá (isEnd = true). Khi query, DFS toàn bộ subtree từ prefix node, dùng min-heap size K để track top-K.

public List<String> topKWithPrefix(String prefix, int k) {
    TrieNode node = walk(prefix);
    if (node == null) return List.of();

    // Min-heap: evict least frequent when size exceeds k.
    PriorityQueue<String> heap = new PriorityQueue<>(
        Comparator.comparingInt(w -> frequencyOf(w))
    );
    dfsCollect(node, new StringBuilder(prefix), heap, k);
    return new ArrayList<>(heap);
}

• Lookup: O(L + matches × log K) — DFS qua subtree.
• Insert: O(L) — đơn giản hơn approach 1.
• Trade-off: query chậm hơn khi subtree lớn, nhưng insert và memory nhẹ hơn.

Chọn gì? Approach 1 phù hợp khi query frequency cao và vocabulary ổn định (search engine autocomplete). Approach 2 phù hợp khi vocabulary thay đổi thường xuyên hoặc K lớn.

7. Pitfall tổng hợp

Pitfall 1 — Unicode alphabet và TrieNode array

Dùng TrieNode[26] chỉ an toàn cho input ASCII a-z. Với Unicode (tiếng Việt, tiếng Nhật, emoji), có thể tới 65.536 code point trong BMP:

// WRONG -- explodes for non-ASCII input like "cà phê" or "東京"
class TrieNode {
    TrieNode[] children = new TrieNode[26];  // assumes a-z only!
    boolean isEnd;
}

// CORRECT -- works for any Unicode character
class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd;
}

TrieNode[65536] mỗi node = 65.536 pointer × 8 bytes = 512KB mỗi node. Với trie 10.000 node, đó là 5GB chỉ cho children array — hoàn toàn không dùng được.

Pitfall 2 — Quên kiểm tra isEnd

Trie chứa ["car", "card"]: khi search "car", walk("car") trả về node "r" không null — nhưng không có nghĩa "car" là một từ hợp lệ nếu không check isEnd.

// WRONG -- returns true even if "car" was never inserted
public boolean search(String word) {
    return walk(word) != null;  // only checks path existence!
}

// CORRECT
public boolean search(String word) {
    TrieNode node = walk(word);
    return node != null && node.isEnd;  // must be marked as word-end
}

Trie chứa ["card"]: walk("car") trả về node "r" với isEnd = false. Đây là "điểm trung gian" trên đường đến "card", không phải từ độc lập. Chỉ node.isEnd mới phân biệt được hai trường hợp.

Pitfall 3 — Delete leak (memory rò rỉ)

Nếu delete chỉ set isEnd = false, các node không dùng trên branch vẫn còn trong memory:

// INCOMPLETE delete -- leaks empty nodes
public void delete(String word) {
    TrieNode node = walk(word);
    if (node != null) node.isEnd = false;  // node and its parents stay in memory!
}

Xử lý đúng: sau khi set isEnd = false, cleanup bottom-up bằng cách xóa các node không còn children và không phải isEnd. Cần thêm logic đệ quy hoặc stack — phức tạp hơn và chỉ cần thiết khi delete thường xuyên. Trong nhiều ứng dụng (search index read-mostly), bỏ qua cleanup là chấp nhận được.

8. Ứng dụng trong các hệ thống thực tế

Linux kernel IP routing table dùng Patricia trie cho longest prefix match. Khi packet đến với destination IP, kernel cần tìm route khớp prefix dài nhất (ví dụ 192.168.1.0/24 cụ thể hơn 192.168.0.0/16). Hash table không hỗ trợ prefix query. Red-Black tree so sánh full key. Patricia trie walk theo từng bit của IP address → O(32) cho IPv4, O(128) cho IPv6 — cực nhanh và độc lập với kích thước routing table.

DNS resolver dùng trie theo cấu trúc domain hierarchy. Domain mail.google.com được resolve theo thứ tự ngược: com → google → mail. Mỗi level tương đương một node trong conceptual trie. Caching DNS khai thác cấu trúc này: cache tại node google.com phục vụ mọi subdomain.

Aho-Corasick — multi-pattern search (Module 7) build một trie của tất cả pattern cần tìm, sau đó thêm "fail links" (tương tự KMP failure function) để xử lý nhiều pattern cùng lúc trong O(text_length + matches). Đây là thuật toán đằng sau grep -r khi search nhiều pattern, và các anti-virus scanner.

Spell checker / autocorrect dùng trie kết hợp Levenshtein automaton. Thay vì check edit distance với từng từ trong dictionary (O(n × L)), traverse trie với state machine tracking edit distance — chỉ explore các nhánh có thể nằm trong threshold edit distance.

Browser URL bar và search suggest box thường dùng trie trên tập URL đã thăm hoặc top queries. Mỗi keystroke là một prefix walk, kết quả là subtree enumeration. Chrome và Firefox giữ trie trong memory để suggest hoạt động ngay lập tức không cần round trip.

9. Deep Dive

10. Tóm tắt

• Trie lưu mỗi ký tự là một node; path từ root đến node lá là một từ. Search prefix = walk path → O(L), độc lập với n.
• Hai cách lưu children: TrieNode[26] (nhanh, lãng phí memory cho sparse alphabet) và HashMap (linh hoạt, phù hợp Unicode).
• isEnd flag bắt buộc: phân biệt "điểm trung gian trên path" với "từ kết thúc tại đây".
• Memory cost worst case O(N × L) — tệ nhất khi nhiều từ ngắn không có prefix chung.
• Patricia/Radix tree nén single-child chain thành edge label, giảm số node đáng kể — dùng trong Linux IP routing, Git, Ethereum.
• Top-K autocomplete: pre-compute top-K per node cho query O(L); lazy DFS + heap cho insert O(L).
• Ứng dụng rộng: autocomplete, IP longest prefix match, DNS, Aho-Corasick, spell checker.

11. Tự kiểm tra

Bài tiếp theo: Bloom filter — probabilistic, false positive math