字典树(Trie)

定义

字典树（Trie，又称前缀树）是一种用于高效存储和检索字符串集合的多叉树。它把字符串的公共前缀合并到同一条路径上，从根到某节点的路径即代表一个前缀。

原理

每个节点代表一个字符，节点的子节点对应可能的后续字符，通常用数组或哈希表保存。一个标记位表示某节点是否为某个完整单词的结尾。查找或插入一个长度为 L 的字符串只需沿路径走 L 步，与集合中字符串数量无关。代价是当字符集大、字符串稀疏时会占用较多内存，可用压缩字典树优化。

复杂度

• 插入：O(L)（L 为字符串长度）
• 查找：O(L)
• 前缀匹配：O(L)
• 空间复杂度：O(节点总数乘字符集大小)

应用场景

• 搜索引擎与输入法的前缀联想
• 自动补全与拼写检查
• IP 路由最长前缀匹配
• 敏感词过滤