Trie 字典树：前缀匹配与字符串检索

前面学字符串时，我们已经知道：文本处理里最常见的不只是“是否相等”，还包括前缀匹配、词典查询、自动补全、多模式检索这些问题。如果每次都把所有字符串放进数组或普通哈希表里，再靠逐个比较去判断前缀关系，很多场景会显得不够自然。Trie，也就是字典树，正是为这类问题设计的一种典型结构。

Trie 最核心的价值在于，它不把整个字符串当成一个不可再分的整体，而是把公共前缀显式组织成共享路径。这样一来：

前缀相同的字符串会走过同一段路径；
查询一个字符串是否存在，变成按字符逐步往下走；
查找某个前缀对应的所有单词，也会变得非常自然。

所以 Trie 并不是普通查找树的字符串版本，它优化的根本不是“关键字大小比较”，而是“字符前缀共享”。这让它在搜索提示、敏感词过滤、路由匹配、词典系统里都非常常见。

一、什么是 Trie

Trie 可以先理解成：

一棵按字符逐层展开的树，每条从根到某个节点的路径，表示一个字符串前缀；从根到某个终止节点的完整路径，则表示一个完整字符串。

例如要存：

cat
car
dog

那么 cat 和 car 会共享前缀 ca，在第三个字符处才分叉；而 dog 则从根的另一条分支展开。

所以 Trie 最关键的特征就是：

相同前缀不会重复存多次；
而是共享为同一路径。

二、Trie 为什么特别适合前缀问题

因为它的结构本身就是围绕前缀组织的。

对于普通哈希表来说：

查完整单词是否存在很方便；
但查某个前缀下有哪些单词，并不天然高效。

而 Trie 中：

走完前缀对应的路径后；
该节点下面的整棵子树，天然就表示所有以这个前缀开头的字符串。

也就是说，Trie 的“结构”直接就是“前缀关系”的可视化表达。

三、Trie 的节点通常存什么

一个 Trie 节点通常至少包含两类信息：

1. 子节点引用集合

表示当前字符后面还能接哪些字符。

2. 终止标记

用于说明：

走到这个节点，是否正好构成一个完整单词；
还是只是某个更长单词的中间前缀。

例如：

存入 app 和 apple 时；
app 结束位置必须能标记“这里是一个完整单词”；
否则就无法区分它只是 apple 的前缀，还是它自己本身也存在。

四、Trie 的核心操作有哪些

1. 插入字符串

从根开始，按字符逐个向下：

有对应分支就沿着走；
没有就新建节点；
最后把终点标记为完整单词结束。

2. 查询完整字符串

同样从根按字符走：

如果中途某个字符路径不存在，则查询失败；
如果路径走完，还要看终止标记是否为真。

3. 查询前缀是否存在

只要能顺利走完整个前缀路径，就说明这个前缀存在。

4. 枚举前缀下所有单词

先找到前缀终点节点，再在该节点子树中做 DFS 或 BFS 即可。

这些操作的时间复杂度通常和字符串长度成正比，而不直接依赖存了多少个字符串。

五、Trie 的复杂度为什么常写成 O(L)

如果要插入或查询一个长度为 L 的字符串，Trie 的过程通常是：

逐字符向下走；
每一层处理一个字符；
总共处理 L 层。

于是：

插入复杂度通常是 O(L)；
查询复杂度通常也是 O(L)。

这很有意思，因为它和“库里已经有多少字符串”关系不大，更关心单词本身长度。

这也是 Trie 在大规模词典场景里很有吸引力的原因之一。

六、Trie 和哈希表相比有什么区别

这是非常值得重点比较的一组。

1. 哈希表

查完整字符串是否存在通常很快；
但前缀查询不天然友好；
无法直接表达前缀共享结构。

2. Trie

查询完整字符串和前缀都很自然；
前缀共享能节省一部分重复存储；
但节点数量可能很多，常数空间开销较大。

所以二者不是谁全面替代谁，而是优化目标不同：

哈希表更偏完整键查找；
Trie 更偏前缀结构问题。

七、Trie 的空间问题为什么很常见

Trie 虽然查找前缀很强，但它有一个典型代价：空间开销可能比较大。

原因在于：

每个节点可能都要维护一组子节点引用；
如果字符集很大，比如全 Unicode；
或者数据分布稀疏；
很多节点会有大量空分支。

所以现实实现里，Trie 通常会做很多空间优化，例如：

用哈希映射代替固定长度数组存孩子；
使用压缩 Trie；
使用双数组 Trie；
用基数树、Patricia Trie 等变体减少节点数量。

八、什么是压缩 Trie 或基数树

普通 Trie 有时会出现很多“单链路径”：

某个节点下面只有唯一一个孩子；
再往下也一直没有分叉；
这样一层一个字符地存，会有点浪费。

于是就可以把一整段连续无分叉路径压缩成一条边，上面存一个字符串片段，而不是单个字符。这类思路通常叫压缩 Trie 或基数树。

本质上仍然是在做同一件事：

继续保留前缀结构，但减少冗余节点。

九、Trie 最典型的应用场景有哪些

1. 自动补全

例如搜索框输入几个字母后，快速给出候选词。

2. 敏感词过滤

把一批模式串建成 Trie，然后在文本流中逐步匹配。

3. 词典系统

查询某个单词是否存在，某个前缀下有哪些词。

4. 路由或路径匹配

例如 URL 路径、命令前缀或某些配置匹配。

5. 多模式匹配的基础结构

例如后面的 Aho-Corasick 自动机，本质上也是建立在 Trie 之上。

十、Trie 和二叉搜索树、B+ 树有何不同

Trie 不依赖大小比较，它不是“按关键字排序再查找”的思路，而是“按字符逐层匹配”。

所以：

BST / 红黑树 / B+ 树更适合通用有序键；
Trie 更适合字符串集合中的前缀和检索问题。

换句话说，它优化的是字符串结构本身，而不是字符序列之间的大小关系。

十一、学习 Trie 时最容易踩的坑

1. 把 Trie 当作普通树背定义

Trie 最重要的不是“它是棵树”，而是“它把前缀关系编码进了结构里”。

2. 忘记终止标记

没有终止标记，就无法区分完整单词和中间前缀。

3. 只看到查询快，不考虑空间开销

Trie 的时间优势往往要用更多节点空间来换。

4. 误以为 Trie 一定比哈希表更好

如果只是完整字符串查存在，哈希表往往更简单直接。

总结

Trie 的重要性，不只是因为它是字符串专题里的常见结构，而是因为它把“前缀关系”直接转成了结构关系。真正值得先建立起来的，是这些核心认识：

Trie 是一种按字符逐层展开、共享公共前缀的树结构；
它特别适合前缀查询、词典检索、自动补全和字符串集合匹配；
插入和查询复杂度通常与字符串长度成正比；
终止标记是区分完整字符串与普通前缀的关键；
Trie 的主要代价通常是空间开销，因此现实里常见各种压缩变体；
真正学会 Trie，不是会写一个模板，而是知道什么时候问题本质上是在问“前缀结构”。

把这一篇理解透之后，后面再去学图、哈希表、多模式匹配和搜索系统时，你会更容易意识到：很多检索问题的关键，不只是“查不查得到”，而是“能不能把共享结构直接编码进存储方式里”。

参考资源：