字典树（进阶）
复习
- 平衡树（进阶）：平衡树通过旋转，让树始终保持矮而匀称
- 堆：父不大于子，堆顶是最值
- 优先队列：每次取出最值
本章为进阶内容，零基础读者可以跳过，不影响后续阅读。
TL;DR
- 字典树按字符逐层组织字符串
- 公共前缀只存一份，节省空间
- 查找代价与字符串长度有关，而非元素个数
- 它特别适合前缀查找与自动补全
正文
如果我们要在一大堆单词里查找，用哈希表通常就够了。可有一类需求，哈希表不太擅长：按前缀查找，比如输入 “app”，想找出所有以它开头的词。这就要请出一种专门的树——字典树（trie）。
一个字一个字符往下走
字典树的想法非常自然：把字符串的每个字符，对应树的一层。
- 根节点代表空串 - 从根往下走一条路径，路径上的字符连起来，就是一个前缀 - 如果某个前缀正好是一个完整单词，就在对应节点上做个标记
比如存 app 和 apple，它们的路径前几个字符完全重合，于是共享同一段前缀，只在后面才分叉。
公共前缀只存一份
这正是字典树最大的好处：大量字符串的公共前缀，只存一份。
保存成千上万个同前缀的单词时（比如一大份英文词典），这种共享能省下可观的空间。相比之下，哈希表是把每个字符串整条存下，前缀重复的部分也各存各的。
当然，字典树的每个节点可能要保存多个指向子节点的指针，在字符集较大时，指针本身也会占不少空间。又是空间与时间的取舍。
代价和什么有关
字典树查找一个键，要沿着它的字符一个个往下走。所以查找代价是 O(m)，其中 m 是字符串的长度——和树里存了多少个元素无关。
这个性质很有用：存一万个词，查一个 5 字母的词，还是走 5 步。
正因如此，字典树特别适合这些场景：
- 自动补全：输入前缀，顺着路径走下去就能找到候选
- 拼写检查：查一个词在不在词典里
- 前缀匹配：网络里的最长前缀匹配，思路就和它相通
你看，前面讲 IP 路由时的“最长前缀匹配”，在这类“按前缀组织”的结构里，也能找到回响。同一个思想，会在不同领域反复出现。
思考题 1
字典树为什么能节省公共前缀的存储空间？
思考题 2
字典树的查找代价，与什么有关、而与什么无关？
小结
知识点
- 字典树按字符逐层组织字符串
- 公共前缀共享，节省空间
- 查找代价为
O(m)，m为字符串长度 - 适合自动补全、拼写检查与前缀匹配
参考资料
- Wikipedia(zh)：Trie：以字符为边组织字符串的树
- Wikipedia(zh)：最长前缀匹配：按前缀组织的匹配思想
思考题答案（仅供参考）
思考题 1
因为它把每个字符作为一层，多个字符串若前缀相同，就沿着同一段路径走，只存一份。分叉只发生在出现不同字符的地方，所以重复的前缀不会被反复存储。
思考题 2
查找代价与字符串的长度有关，需要沿字符逐个往下走，是 O(m)；而与树中元素的总数无关，无论存了多少个词，查一个长度为 m 的词都只走 m 步。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪