字典树（Trie）算法通关指南：前缀树原理、Python 实现与 LeetCode 实战（AlgoNote）

教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文以 AlgoNote 仓库 04_08_trie.md 为主体系统讲解字典树Trie前缀树的数据结构原理、节点与整体结构设计、插入 / 查找 / 前缀查询三大核心操作并结合仓库源码 string_trie.py 与 6 道 LeetCode 题解给出可直接运行的 Python 实现。读完本文你将掌握字典树两种节点存储方式数组 / 哈希表的取舍、复杂度分析方法并能把 Trie 应用到字符串检索、前缀统计、最长公共前缀与搜索自动补全等实战场景。1. 字典树介绍字典树Trie又称前缀树是一种高效存储和查找字符串集合的树形结构。可以把它想象成一本「分层字典」每个单词从根节点出发按字母顺序一层层分支直到单词结尾。具有相同前缀的单词会在树上共用同一条路径就像家族树中有共同祖先的亲戚一样这样能大幅提升查找和前缀匹配的效率。例如将a、abc、acb、acc、ach、b、chb这 7 个单词存入一棵字典树后边表示字符从根节点到某节点的路径即为一个单词例如1 → 2 → 6 → 10表示acc每个单词的结尾节点通常带有一个结束标记end红色节点用于区分「完整单词」与「只是某单词的前缀」。字典树的本质是利用字符串的公共前缀将相同前缀的单词合并存储从而加快查询速度、减少重复比较是典型的「空间换时间」策略。1.1 字典树的基本性质根节点不存字符其他每个节点只存一个字符从根到某节点的路径组成该节点对应的字符串每个节点的所有子节点字符都不相同。1.2 适用字符集与前提在 AlgoNote 的实践场景LeetCode 字符串类题目中Trie 通常用于仅含小写英文字母字符集大小 $d26$的字符串集合仅含小写字母与数字的组合字符集任意字符集借助哈希表实现。字符集大小直接决定节点存储结构的选择详见 2.1 节。2. 字典树的基本操作字典树常见的基本操作包括创建、插入、查找和删除。其中删除操作在实际应用中较少用到如需删除通常采用懒删除标记或对isEnd做计数处理因此本节主要聚焦于字典树的创建、插入和查找。2.1 字典树的结构2.1.1 字典树节点的定义字典树本质上是一棵多叉树即每个节点可以拥有多个子节点。实现多叉结构时常见的方式有两种数组或哈希表。方式一定长数组适用于小写字母字符集当字符串仅包含小写英文字母时可以用长度为 26 的数组来存储每个节点的所有子节点class Node: # 字符节点 def __init__(self): # 初始化字符节点 # children 是长度为 26 的数组分别对应 a~z 的子节点 self.children [None for _ in range(26)] # 初始化所有子节点为 None self.isEnd False # isEnd 用于标记该节点是否为某个单词的结尾其中self.children采用数组结构表示该节点的全部子节点isEnd用于标记该节点是否为某个单词的结尾。在插入单词时需要将每个字符转换为对应的数字索引ord(ch) - ord(a)然后在长度为 26 的数组中定位并创建相应的子节点。数组实现的下标访问是 $O(1)$ 的但每个节点都要预先开辟 26 个槽位空间开销固定且偏大。方式二哈希表适用于任意字符集如果字符集不仅包含小写字母还包括大写字母或其他字符则可使用哈希表来存储当前节点的所有子节点class Node: # 字符节点 def __init__(self): # 初始化字符节点 self.children dict() # 用哈希表存储所有子节点key 为字符value 为 Node 实例 self.isEnd False # 标记该节点是否为某个单词的结尾 # 例如children[a] 表示以当前节点为父节点字符为 a 的子节点上述代码中self.children采用哈希表结构用于存储该节点的所有子节点isEnd用于标记该节点是否为某个单词的结尾。插入单词时可以根据单词的每个字符动态创建对应的字符节点并将其加入哈希表便于高效查找和插入——只有真正用到的字符才会创建子节点因此更节省空间。两种方式的取舍对比维度数组实现哈希表实现字符集支持需预先确定字符集如 26 个小写字母任意字符集子节点查询$O(1)$ 下标访问$O(1)$ 平均哈希查找空间占用固定 26 个槽位稀疏时浪费按需创建节省空间遍历子节点需要遍历 26 个位置并判空直接遍历字典的 value 集合仓库源码 string_trie.py 采用的就是哈希表实现self.children dict()与 04_08_trie.md 中的约定一致。为统一实现和便于维护本文后续所有代码均采用哈希表来管理节点的子节点。2.1.2 字典树的基本结构在明确了字典树节点的结构后进一步定义字典树的整体结构。字典树在初始化时会创建一个根节点该根节点不存储任何字符所有的插入和查找操作均从根节点出发class Trie: # 字典树前缀树 def __init__(self): 初始化字典树创建一个根节点。 根节点不存储任何字符仅作为所有单词的公共起点。 self.root Node() # 初始化根节点根节点不保存字符2.2 字典树的创建与插入操作字典树的「创建」是指将字符串数组中的所有字符串依次插入到字典树中而「插入」操作则是将单个字符串加入到字典树的过程。2.2.1 字典树的插入操作在介绍字典树的批量创建前先说明单个单词的插入流程从根节点出发依次遍历单词的每个字符ch根节点本身不存储字符如果当前节点的子节点中不存在字符ch则新建一个节点cur.children[ch] Node()并将当前指针移动到新节点如果当前节点的子节点中已存在字符ch则直接将当前指针移动到该子节点当所有字符遍历完毕后将当前节点标记为单词结尾即isEnd True。# 向字典树中插入一个单词 def insert(self, word: str) - None: 将一个单词插入到字典树中。 参数: word (str): 需要插入的单词 cur self.root # 从根节点开始 for ch in word: # 遍历单词中的每个字符 # 如果当前节点的子节点中不存在字符 ch则新建一个节点 if ch not in cur.children: cur.children[ch] Node() # 创建新节点并加入子节点字典 # 移动到下一个字符节点继续插入 cur cur.children[ch] # 单词所有字符插入完成后将当前节点标记为单词结尾 cur.isEnd True2.2.2 字典树的创建操作字典树的创建过程比较简单通常包括以下步骤先实例化一个字典树对象如trie Trie()遍历单词列表将每个单词依次插入到字典树中。# 创建一个字典树实例 trie Trie() # 遍历单词列表将每个单词插入到字典树中 for word in words: trie.insert(word)插入后具有公共前缀的单词会共享路径例如先插入apple再插入app前三个字符a-p-p不会产生新的节点只有apple独有的l-e会新增节点这是字典树空间共享的核心体现。2.3 字典树的查找操作2.3.1 字典树的查找单词操作在字典树中查找某个单词是否存在的过程与插入操作类似具体步骤如下从根节点出发依次遍历单词的每个字符ch如果当前节点的子节点中不存在字符ch则说明该单词不在字典树中直接返回False如果存在字符ch则将当前指针移动到对应的子节点继续查找下一个字符当所有字符遍历完毕后检查当前节点是否被标记为单词结尾isEnd True。如果是则说明字典树中存在该单词返回True否则返回False。# 查找字典树中是否存在一个单词 def search(self, word: str) - bool: 在字典树中查找指定单词是否存在。 参数: word (str): 需要查找的单词 返回: bool: 如果单词存在于字典树中返回 True否则返回 False cur self.root # 从根节点开始 for ch in word: # 遍历单词中的每个字符 if ch not in cur.children: # 如果当前节点的子节点中不存在该字符 return False # 说明单词不存在直接返回 False cur cur.children[ch] # 移动到对应的子节点继续查找下一个字符 return cur.isEnd # 所有字符查找完毕判断当前节点是否为单词结尾标记注意search(app)与search(apple)的区别就在最后一步——若树中只插入过apple则app遍历完后所在的节点isEnd为False因此查找结果为False。这正是isEnd结束标记存在的意义。仓库源码 string_trie.py 中写法为return cur is not None and cur.isEnd额外判空使其在更严谨的边界场景下同样安全。2.3.2 字典树的查找前缀操作在字典树中查找某个前缀是否存在其过程与查找完整单词类似。不同之处在于查找前缀时只需依次判断每个字符是否存在于相应的子节点中无需判断最后节点是否为单词结尾标记。只要前缀的所有字符都能顺利匹配即可认为该前缀存在于字典树中。# 查找字典树中是否存在一个前缀 def startsWith(self, prefix: str) - bool: 在字典树中查找指定前缀是否存在。 参数: prefix (str): 需要查找的前缀字符串 返回: bool: 如果前缀存在于字典树中返回 True否则返回 False cur self.root # 从根节点开始 for ch in prefix: # 遍历前缀中的每个字符 if ch not in cur.children: # 如果当前节点的子节点中不存在该字符 return False # 说明前缀不存在直接返回 False cur cur.children[ch] # 移动到对应的子节点继续查找下一个字符 return True # 所有字符查找完毕前缀存在于字典树中search与startsWith的差异可以一句话概括查单词要看isEnd查前缀只需路径可达。3. 字典树的完整实现代码将上述节点定义与三个核心方法整合即得到一份可直接运行的完整实现与仓库源码 string_trie.py 保持一致class Node: # 字符节点Trie 树的节点 def __init__(self): self.children dict() # 子节点字典key 为字符value 为 Node 对象 self.isEnd False # 是否为单词结尾标记 class Trie: # 字典树Trie def __init__(self): 初始化字典树创建一个空的根节点根节点不保存字符 self.root Node() def insert(self, word: str) - None: 向字典树中插入一个单词 参数: word (str): 要插入的单词 cur self.root # 从根节点开始 for ch in word: # 遍历单词中的每个字符 if ch not in cur.children: # 如果当前节点没有ch这个子节点 cur.children[ch] Node() # 新建一个子节点 cur cur.children[ch] # 移动到子节点继续处理下一个字符 cur.isEnd True # 单词插入完成标记结尾 def search(self, word: str) - bool: 查找字典树中是否存在一个完整单词 参数: word (str): 要查找的单词 返回: bool: 存在返回True否则返回False cur self.root # 从根节点开始 for ch in word: # 遍历单词中的每个字符 if ch not in cur.children: # 如果没有对应的子节点 return False # 单词不存在 cur cur.children[ch] # 移动到子节点 return cur.isEnd # 判断是否为单词结尾 def startsWith(self, prefix: str) - bool: 查找字典树中是否存在某个前缀 参数: prefix (str): 要查找的前缀 返回: bool: 存在返回True否则返回False cur self.root # 从根节点开始 for ch in prefix: # 遍历前缀中的每个字符 if ch not in cur.children: # 如果没有对应的子节点 return False # 前缀不存在 cur cur.children[ch] # 移动到子节点 return True # 前缀存在3.1 代码的 LeetCode 兼容性说明上述insert / search / startsWith的 API 签名与 LeetCode 0208「实现 Trie前缀树」的接口完全一致。仓库题解 implement-trie-prefix-tree.md 给出了同构实现并补充了题目约束word和prefix长度不超过 2000三种操作总调用次数不超过 $3 \times 10^4$ 次可直接用于作答。3.2 变体节点即字典树自引用实现部分题解如 design-add-and-search-words-data-structure.md、map-sum-pairs.md采用另一种写法让Trie类自身兼任节点即self.children dict()与self.isEnd直接定义在Trie实例上insert时cur.children[ch] Trie()。这种写法省去了Node类代码更紧凑原理完全相同读者可根据习惯二选一。4. 字典树的算法分析指标复杂度说明插入一个单词时间$O(n)$空间$O(d^n)$数组实现空间$O(n)$哈希表实现$n$ 为单词长度$d$ 为字符集大小。数组实现空间消耗大哈希表实现更节省空间。查找一个单词时间$O(n)$空间$O(1)$$n$ 为单词长度仅遍历单词长度空间为常数。查找一个前缀时间$O(m)$空间$O(1)$$m$ 为前缀长度仅遍历前缀长度空间为常数。补充说明时间复杂度的核心优势无论字典中存储了多少个单词插入 / 查找 / 前缀查询的时间都只与当前字符串本身的长度有关而与字典规模无关——这是 Trie 相比「遍历所有字符串逐一比对」的暴力方案最本质的改进。题解 implement-trie-prefix-tree.md 给出的整体空间复杂度为 $O(|T| \times \sum)$其中 $|T|$ 是所有插入字符串的长度之和$\sum$ 是字符集大小空间开销的差异数组实现中每个节点固定占 26 个槽位整棵树的最坏空间可膨胀到 $O(d^n)$$d26$ 时尤其明显哈希表实现只在实际创建子节点时分配空间稀疏字符集下更省内存这正是本文选用哈希表实现的直接原因。5. 字典树的应用字典树一个典型的应用场景就是在搜索引擎中输入部分内容之后搜索引擎会自动弹出一些关联的相关搜索内容。我们可以从中直接选择自己想要搜索的内容而不用将所有内容都输入进去。这个功能从一定程度上节省了我们的搜索时间。这个功能实现的基本原理就是字典树用户输入的前缀沿着根节点往下匹配凡是能够走通的路径对应的节点其子树中所有标记了isEnd的单词都是候选的补全结果。当然像 Google、必应、百度这样的搜索引擎在这个功能背后肯定做了大量的改进和优化如倒排索引、热度排序、模糊纠错等但其底层最基本的原理就是「字典树」这种数据结构。除此之外可以把字典树的应用分为以下几种字符串检索事先将已知的一些字符串字典的有关信息存储到字典树里查找一些字符串是否出现过、出现的频率可仿照 map-sum-pairs.md 在节点上附加value计数前缀统计统计一个串所有前缀单词的个数只需统计从根节点到叶子节点路径上单词出现的个数也可以判断一个单词是否为另一个单词的前缀最长公共前缀问题LCP利用字典树求解多个字符串的最长公共前缀问题。将大量字符串都存储到一棵字典树上时可以快速得到某些字符串的公共前缀。对所有字符串都建立字典树后两个串的最长公共前缀的长度就是它们所在节点最近公共祖先LCA的深度于是问题转变为最近公共祖先问题字符串排序利用字典树进行串排序。例如给定多个互不相同的仅由一个单词构成的英文名将它们按字典序从小到大输出。采用数组方式创建字典树时字典树中每个节点的所有子节点天然按照字母大小排序下标即字母序然后对字典树进行先序遍历输出的相应字符串就是按字典序排序的结果。6. 字典树与其他数据结构的对比从源码结构与题解应用看与 Trie 形成竞争关系的主要是哈希表哈希表查询任意完整字符串是 $O(1)$ 平均复杂度非常快但无法回答「有哪些字符串以某前缀开头」这类前缀查询除非额外维护所有前缀索引开销极大字典树完整字符串查询为 $O(n)$$n$ 为串长虽然常数上略慢于哈希表但天然支持前缀匹配、字典序遍历、LCP 查询且共享前缀节省存储。因此在实际工程中两者常互补使用哈希表用于精确 O(1) 命中Trie 用于前缀相关的检索需求。7. 总结字典树Trie是一种高效存储和查找字符串集合的树形数据结构通过利用字符串的公共前缀来减少重复比较实现快速的前缀匹配和字符串检索。优点查找效率高查找单词和前缀的时间复杂度均为 $O(n)$其中 $n$ 为字符串长度比暴力匹配快很多前缀匹配优秀能够快速判断一个字符串是否为另一个字符串的前缀这在搜索引擎自动补全等场景中非常有用空间共享具有相同前缀的单词共享路径相比单独存储每个单词能节省大量空间支持动态操作可以动态插入、删除字符串适合需要频繁更新的字符串集合。缺点空间消耗较大每个节点都需要存储子节点信息对于稀疏的字符串集合空间利用率不高数组实现尤其明显实现复杂度相比简单的哈希表或数组字典树的实现和维护更加复杂字符集限制使用数组实现时字符集大小会影响空间复杂度大字符集会显著增加内存消耗缓存不友好树形结构在内存中的分布可能不够连续对 CPU 缓存不够友好。8. 练习题目仓库题解索引以下题目均可在仓库 docs/solutions 目录下找到完整题解建议按「先掌握核心 API → 再进阶带.通配 → 再到节点附加数值 / 前缀替换」的顺序练习0208. 实现 Trie前缀树Trie 三件套insert/search/startsWith的模板题直接套用本文第 3 节代码即可通过0211. 添加与搜索单词 - 数据结构设计在search中支持.通配符遇到.时需要递归 DFS遍历当前节点的所有子节点是 Trie 与深度优先搜索结合的代表题0677. 键值映射在 Trie 节点上附加value字段sum(prefix)先定位前缀节点再递归累加子树所有节点的value对应「前缀统计」应用0648. 单词替换把所有词根插入 Trie对句子中每个单词沿路径匹配一旦遇到isEnd即取最短词根替换对应「字符串检索 前缀匹配」应用0676. 实现一个魔法字典构建字典后枚举searchWord每个位置替换为其余 25 个字母并在 Trie 中查询注意替换后的字符必须不同于原字符1023. 驼峰式匹配将pattern插入 Trie匹配查询串时小写字母可跳过、大写字母必须命中综合考察字符分类与 Trie 匹配。如需按专题批量刷题可参考仓库的 字典树题目分类列表其中整理了完整的 Trie 相关题单。参考资料【书籍】算法训练营 陈小玉 著【书籍】ACM-ICPC 程序设计系列 算法设计与实现 陈宇 吴昊 主编【开源实现】string_trie.py 字典树 Python 源码AlgoNote 仓库【题解】0208. 实现 Trie前缀树 等 6 篇字典树专题题解AlgoNote 仓库赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐Learn-Algorithms 字典树Trie / 前缀树精讲原理、存储结构与 C 语言实现Learn Algorithms 字典树Trie / 前缀树精讲原理、存储结构与 C 语言实现 字典树Trie又称前缀树、单词查找树是一种利用字符串教程Swift Algorithm Club 之 Trie 字典树Swift 前缀树数据结构的原理与实现详解Swift Algorithm Club 之 Trie 字典树Swift 前缀树数据结构的原理与实现详解 导读 Trie又称前缀树 prefix tree、示例工程教程3步上手copyparty文件服务器主题定制CSS变量完整指南3步上手copyparty文件服务器主题定制CSS变量完整指南 copyparty 是一个把断点续传、WebDAV、SFTP、媒体索引全塞进单文件的便携式文件后端存储网络通信上一篇DevPod Provider开发指南自定义后端支持下一篇FinRL金融强化学习教学案例集高校AI金融课程应用终极指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考