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

Question

IT Interview Practice · 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ả.

Cấu trúc

Code

Độ phức tạp

Đánh đổi

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

Câu hỏi liên quan