1106 字
6 分钟
字典树：前缀匹配的终极数据结构
概述
Trie，也叫字典树或前缀树，是一种专门处理字符串前缀的数据结构。它把单词拆成字符路径，共享相同前缀的单词会共用同一段节点。
如果需要频繁做“是否存在某个单词”“是否存在某个前缀”“根据输入前缀自动补全”，Trie 比逐个字符串扫描更自然。
它的核心思想是：用树的路径表示字符串。
前置知识
- 树结构：每条边表示一个字符
- 哈希表 / 数组：节点子链接可用 Map 或数组存储
- 前缀匹配：查询过程沿字符逐层向下
问题定义
假设有三个单词：
catcardogTrie 会把它们组织成：
root├─ c│ └─ a│ ├─ t (word)│ └─ r (word)└─ d └─ o └─ g (word)这样查询前缀 ca 时，只需要走 c -> a，就能知道有哪些单词共享这个前缀。
Trie 适合的问题：
| 需求 | 普通数组 | Trie |
|---|---|---|
| 判断单词是否存在 | O(n * L) | O(L) |
| 判断前缀是否存在 | O(n * L) | O(L) |
| 自动补全 | 需要扫描所有单词 | 定位前缀后遍历子树 |
其中 L 是单词长度，n 是单词数量。
核心原理：分步图解
插入单词
插入 cat：
root -> c -> a -> t如果路径不存在，就创建节点；如果路径已存在，就复用节点。最后在 t 节点标记“这里是一个完整单词”。
查询单词
查询 car：
- 从 root 出发；
- 依次查找
c、a、r； - 如果路径断开，单词不存在；
- 如果路径存在，还要检查最后节点是否标记为完整单词。
查询前缀
查询前缀只需要路径存在，不要求最后节点是完整单词。
这就是 search("ca") 和 startsWith("ca") 的区别。
算法精细步骤
Trie 节点通常包含：
children: 当前字符到子节点的映射isWord: 是否在这里结束一个完整单词插入流程：
- 从根节点开始；
- 遍历单词的每个字符；
- 如果当前字符没有对应子节点，就创建；
- 移动到子节点；
- 遍历结束后标记
isWord = true。
查询流程类似，只是不创建节点；遇到缺失路径直接返回失败。
TypeScript 实现
class TrieNode { readonly children = new Map<string, TrieNode>(); isWord = false;}
class Trie { private readonly root = new TrieNode();
insert(word: string): void { let node = this.root;
for (const char of word) { let next = node.children.get(char);
if (!next) { next = new TrieNode(); node.children.set(char, next); }
node = next; }
node.isWord = true; }
search(word: string): boolean { const node = this.findNode(word); return node?.isWord ?? false; }
startsWith(prefix: string): boolean { return this.findNode(prefix) !== null; }
suggest(prefix: string, limit = 10): string[] { const start = this.findNode(prefix); if (start === null) return [];
const result: string[] = [];
const dfs = (node: TrieNode, path: string): void => { if (result.length >= limit) return; if (node.isWord) result.push(path);
for (const [char, child] of node.children) { dfs(child, path + char); } };
dfs(start, prefix); return result; }
private findNode(text: string): TrieNode | null { let node = this.root;
for (const char of text) { const next = node.children.get(char); if (!next) return null; node = next; }
return node; }}工程优化：压缩 Trie
标准 Trie 的节点数可能很多，尤其当字符串很长且分支较少时，会产生大量只有一个子节点的节点。
例如：
root -> a -> p -> p -> l -> e如果中间节点没有分叉，可以压缩成：
root -> "apple"这类结构叫压缩 Trie 或 Radix Tree。它减少节点数量，但实现更复杂，需要处理字符串片段的拆分和匹配。
工程中是否压缩，取决于数据规模、内存压力和查询性能要求。
应用与局限
典型应用
- 搜索框自动补全；
- 敏感词匹配；
- 拼写检查；
- 路由匹配；
- IP 前缀匹配；
- 单词游戏和词典查询。
局限性
- 相比哈希表，Trie 占用更多节点对象；
- 字符集越大，子节点映射越复杂；
- 删除单词需要清理无用节点；
- 只适合前缀相关问题，不适合任意子串匹配。
总结
graph LR
A[插入字符串] --> B[逐字符建边]
B --> C[标记单词结束]
C --> D[查询单词或前缀]- Trie 用树路径表示字符串。
- 共享前缀是 Trie 的核心优势。
search要求完整单词存在，startsWith只要求路径存在。- 自动补全可以先定位前缀节点，再遍历子树。
- 数据量大时要关注节点数量和压缩策略。
字典树：前缀匹配的终极数据结构
https://www.hehonglei.cn/technology/trie/