前端知识库字典树基础知识速览
用前缀树组织字符串集合，理解关键词匹配、前缀查询和复杂度边界。
约 2 分钟算法 · 字典树 · Trie · 字符串 · 复杂度
字典树基础知识速览
一、字典树解决什么问题
字典树（Trie，也叫前缀树）按字符的公共前缀组织字符串。它适合处理“词典固定、查询很多、查询与前缀有关”的问题，例如关键词联想、敏感词检测、路由前缀匹配和字典序遍历。
它不是所有字符串查询的默认选择：只比较完整字符串时，哈希表通常更简单；需要子串搜索、通配符或复杂正则时，应比较 Aho-Corasick、后缀结构或专用搜索索引。
二、核心结构
每个节点代表一段前缀，边代表一个字符，terminal 表示某个词在此结束：
词典：app、apple、bat
(root)
├─ a ─ p ─ p* ─ l ─ e*
└─ b ─ a ─ t*
* 不是额外字符，而是“这里有一个完整词”的标记。因此 app 是 apple 的前缀，但不能因为走到了 app 节点就把 apple 当成已匹配。
三、复杂度口径
设单词长度为 L，词典总字符数为 S：
- 插入一个单词：
O(L)； - 查询一个完整单词或前缀：
O(L)； - 构建整棵树：
O(S)； - 空间：最坏
O(S)，但节点对象和字符映射会有额外常数。
对大量短词，数组子节点访问快但占用空间大；Map/对象子节点更节省稀疏节点空间，却有更高的对象和哈希开销。工程上应根据字符集、词典规模和内存预算选择表示，并用真实数据测量。
四、学习顺序
- 先实现插入和完整词查询，确认
terminal边界。 - 再实现前缀查询和 DFS 遍历。
- 最后处理重复词、大小写/Unicode 归一化、匹配重叠和大词典内存问题。