什么是 trie（前缀树），何时使用它？

Question

Accepted Answer

**trie**（前缀树）是一棵树，其中每条**边**代表一个字符，从**根出发的每条路径**都拼写出一个前缀。共享前缀的单词共享同一条路径，使得前缀查询极其迅速。

## 结构

```text
Insert "cat", "car", "dog":
        root
       /    \
      c      d
      |      |
      a      o
     / \     |
    t*  r*   g*       (* marks end-of-word)
```

## 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 = word length
        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
```

## Complexity

| Operation | Time |
|---|---|
| insert | O(L) |
| search | O(L) |
| prefix query | O(L) |

关键的是，时间复杂度取决于**单词长度 L**，*而非*存储的单词数量。

## Trade-offs

- **优势：** 快速前缀搜索；自动完成；共享前缀为相似单词节省空间。
- **劣势：** 每个节点的内存开销大（每个节点需要一个子节点映射）；对于无关键字，可能比哈希集合占用更多空间。

## 为什么这很重要

Trie 为自动完成、拼写检查器、IP 路由表和基于字典的搜索提供支持，其中**前缀**匹配至关重要。

当哈希集合只能回答