前缀树(Trie)

前缀树(Trie)又称字典树或单词查找树,是一种专门用于存储字符串集合的树形数据结构。它的核心思想是把具有相同前缀的字符串共享同一条路径,从而实现快速的前缀匹配和检索。Trie 这个名称来源于英文单词 retrieval(检索)。

概述

与哈希表相比,前缀树的查询效率只取决于键的长度,而与集合中元素的总数无关,并且天然支持前缀查询这种哈希表难以高效完成的操作。它的每条从根到某节点的路径就对应一个字符串前缀,叶子或带标记的节点表示一个完整的词。

核心原理

• 根节点不存储字符,从根到任意节点的路径拼接起来代表一个字符串前缀。
• 每个节点的子节点按字符区分,插入字符串时沿着字符逐层向下,不存在则新建节点。
• 用一个标记位表示某节点是否为某个完整单词的结尾。
• 查找时沿字符路径下行,若中途路径缺失则说明该串不存在。

基本前缀树在字符集较大时会占用较多空间,因此衍生出压缩前缀树(基数树)、双数组 Trie 等优化结构,以节省内存并加速访问。

应用场景

• 搜索框的输入自动补全和联想提示。
• 拼写检查和词典查询。
• IP 路由表的最长前缀匹配。
• 敏感词过滤、字符串前缀统计等文本处理任务。

常见问题

问:前缀树和哈希表如何取舍?答:哈希表适合精确的单键查询,平均常数时间;前缀树则擅长前缀匹配、有序遍历和范围查询。若业务需要按前缀检索或排序输出,前缀树更合适。

问:前缀树的主要缺点是什么?答:当字符集很大或字符串稀疏时,节点会包含大量空指针,内存占用较高。可以用压缩前缀树或双数组等结构来降低空间开销。