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

TL;DR: Trie (đọc như "try") là cây mà mỗi node đại diện cho một ký tự — path từ root đến một node là một prefix. Tìm prefix = đi theo path O(L) hoàn toàn độc lập với n (số từ đã lưu), trong khi HashMap phải scan toàn bộ O(n×L). Hai pitfall lớn nhất: dùng mảng [26] khi alphabet có dấu (Unicode), và quên kiểm tra isEnd sau walk nên nhầm "node trung gian" với "từ hợp lệ". Patricia/Radix tree nén single-child chain thành edge label — dùng trong Linux IP routing, Git, Ethereum.

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.

Cấu trúc node:
  TrieNode:
    children: Map<ký_tự, TrieNode>   -- map từ ký tự sang node con
    isEnd: boolean                   -- true nếu node này kết thúc một từ hợp lệ

  -- Khởi tạo: children rỗng, isEnd = false

Trade-off Map<ký_tự, Node> vs mảng [26]:

Với Unicode (65k+ character), mảng [65536] sẽ tốn khoảng 256KB mỗi node — hoàn toàn không khả thi. Dùng HashMap cho alphabet rộng.

3. Insert, Search, và startsWith

-- Insert từ vào trie
insert(root, word):
    node <- root
    for each ký_tự c trong word:
        if c không trong node.children:
            node.children[c] <- TrieNode mới
        node <- node.children[c]
    node.isEnd <- true              -- đánh dấu cuối từ

Time: O(L)  Space: O(L) cho các node mới trên path

-- Tìm kiếm chính xác từ trong trie
search(root, word):
    node <- walk(root, word)
    -- phải đến được node VÀ node đó phải là điểm kết thúc từ
    return node != null và node.isEnd = true

Time: O(L)  Space: O(1)

-- Kiểm tra prefix có tồn tại không
startsWith(root, prefix):
    -- chỉ cần đến được node prefix -- không cần kiểm tra isEnd
    return walk(root, prefix) != null

Time: O(L)  Space: O(1)

-- Đi xuống trie theo từng ký tự của s
-- Trả về node đến được, hoặc null nếu path không tồn tại
walk(root, s):
    node <- root
    for each ký_tự c trong s:
        if c không trong node.children:
            return null
        node <- node.children[c]
    return node

Sơ đồ trie sau khi insert ["car", "cart", "cat", "can", "dog"]:

graph TD
    ROOT(("root"))
    C(("c"))
    D(("d"))
    CA(("a"))
    DO(("o"))
    CAR["r ✓"]
    CAT["t ✓"]
    CAN["n ✓"]
    CART["t ✓"]
    DOG["g ✓"]
    ROOT --> C
    ROOT --> D
    C --> CA
    D --> DO
    CA --> CAR
    CA --> CAT
    CA --> CAN
    CAR --> CART
    DO --> 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 không có nhánh: i-n-t-e-r
                    ├── e
                    │   └── s
                    │       └── t [isEnd]  ("interest")
                    │           └── i
                    │               └── n
                    │                   └── g [isEnd]  ("interesting")
                    └── n
                        └── a
                            └── l [isEnd]  ("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]   ("interest")
    │   └── "ing" [isEnd]  ("interesting")
    └── "nal" [isEnd]   ("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:

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.

AutocompleteNode:
    children: Map<ký_tự, AutocompleteNode>
    isEnd: boolean
    topK: List<String>   -- K từ phổ biến nhất có thể reach từ node này

• 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.

topKWithPrefix(root, prefix, k):
    node <- walk(root, prefix)
    if node = null: return []

    heap <- MinHeap(capacity=k, key=frequency)  -- loại bỏ freq thấp nhất khi đầy
    dfsCollect(node, heap, k)
    return heap.toList()

Time: O(L + matches × log K)  Space: O(k)

• 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à mảng cố định kích thước

Dùng mảng 26 phần tử 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:

-- SAI: nổ khi gặp ký tự ngoài a-z (Latin có dấu, CJK, emoji)
TrieNode:
    children: mảng[26]    -- chỉ dành cho a-z!
    isEnd: boolean

-- ĐÚNG: xử lý được mọi ký tự Unicode
TrieNode:
    children: HashMap<ký_tự, TrieNode>
    isEnd: boolean

Mảng 65.536 phần tử mỗi node = 65.536 pointer × 8 byte = 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.

-- SAI: trả về true dù "car" chưa được insert
search(root, word):
    return walk(root, word) != null    -- chỉ kiểm tra path tồn tại!

-- ĐÚNG: phải kiểm tra cả isEnd
search(root, word):
    node <- walk(root, word)
    return node != null và node.isEnd = true

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:

-- CHƯA ĐẦY ĐỦ: bị rò rỉ node rỗng
delete(root, word):
    node <- walk(root, word)
    if node != null:
        node.isEnd <- false    -- node và các node cha vẫn còn trong 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 (Thuật toán Ứng dụng — Module 2) 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: mảng [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