Trie (prefix tree) là gì và khi nào nó hữu ích?

Question

Accepted Answer

**Trie** (prefix tree — cây tiền tố) là một cây trong đó mỗi **cạnh (edge)** đại diện cho một ký tự và mỗi **đường đi từ root** đánh vần một tiền tố (prefix). Các từ chia sẻ một tiền tố sẽ chia sẻ cùng đường đi, khiến việc tra cứu tiền tố cực kỳ nhanh.

## Cấu trúc

```text
Chèn "cat", "car", "dog":
        root
       /    \
      c      d
      |      |
      a      o
     / \     |
    t*  r*   g*       (* đánh dấu kết thúc từ)
```

## Code

```python
class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):           # O(L), L = độ dài từ
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True
    def starts_with(self, prefix):    # O(L)
        node = self.root
        for ch in prefix:
            if ch not in node.children: return False
            node = node.children[ch]
        return True
```

## Độ phức tạp

| Thao tác | Thời gian |
|---|---|
| insert | O(L) |
| search | O(L) |
| truy vấn tiền tố | O(L) |

Quan trọng là, chi phí phụ thuộc vào **độ dài từ L**, *không phải* số lượng từ được lưu.

## Đánh đổi

- **Điểm mạnh:** tìm kiếm tiền tố nhanh; autocomplete; tiền tố chia sẻ tiết kiệm không gian cho các từ tương tự.
- **Điểm yếu:** chi phí bộ nhớ cao mỗi node (một child map cho mỗi node); có thể dùng nhiều không gian hơn hash set cho các key không liên quan.

## Tại sao điều này quan trọng

Trie cấp năng lượng cho autocomplete, trình kiểm tra chính tả, bảng định tuyến IP, và tìm kiếm dựa trên từ điển nơi khớp **tiền tố** quan trọng.

Khi một hash set chỉ trả lời "khớp chính xác," một trie còn trả lời thêm "những từ nào bắt đầu bằng X?" một cách hiệu quả.