字典树（Trie）算法通关指南：前缀树原理、Python 实现与 LeetCode 实战（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 通常用于：

• 仅含小写英文字母（字符集大小 $d=26$）的字符串集合；
• 仅含小写字母与数字的组合字符集；
• 任意字符集（借助哈希表实现）。

字符集大小直接决定节点存储结构的选择，详见 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用于标记该节点是否为某个单词的结尾。插入单词时，可以根据单词的每个字符动态创建对应的字符节点，并将其加入哈希表，便于高效查找和插入——只有真正用到的字符才会创建子节点，因此更节省空间。

两种方式的取舍：

仓库源码 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 字典树的插入操作

在介绍字典树的批量创建前，先说明单个单词的插入流程：

1. 从根节点出发，依次遍历单词的每个字符ch（根节点本身不存储字符）；
2. 如果当前节点的子节点中不存在字符ch，则新建一个节点cur.children[ch] = Node()，并将当前指针移动到新节点；
3. 如果当前节点的子节点中已存在字符ch，则直接将当前指针移动到该子节点；
4. 当所有字符遍历完毕后，将当前节点标记为单词结尾（即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 = True

2.2.2 字典树的创建操作

字典树的创建过程比较简单，通常包括以下步骤：

1. 先实例化一个字典树对象，如trie = Trie()；
2. 遍历单词列表，将每个单词依次插入到字典树中。

# 创建一个字典树实例 trie = Trie() # 遍历单词列表，将每个单词插入到字典树中 for word in words: trie.insert(word)

插入后，具有公共前缀的单词会共享路径：例如先插入"apple"再插入"app"，前三个字符a-p-p不会产生新的节点，只有"apple"独有的l-e会新增节点，这是字典树空间共享的核心体现。

2.3 字典树的查找操作

2.3.1 字典树的查找单词操作

在字典树中查找某个单词是否存在的过程与插入操作类似，具体步骤如下：

1. 从根节点出发，依次遍历单词的每个字符ch；
2. 如果当前节点的子节点中不存在字符ch，则说明该单词不在字典树中，直接返回False；
3. 如果存在字符ch，则将当前指针移动到对应的子节点，继续查找下一个字符；
4. 当所有字符遍历完毕后，检查当前节点是否被标记为单词结尾（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. 字典树的算法分析

补充说明：

• 时间复杂度的核心优势：无论字典中存储了多少个单词，插入 / 查找 / 前缀查询的时间都只与当前字符串本身的长度有关，而与字典规模无关——这是 Trie 相比「遍历所有字符串逐一比对」的暴力方案最本质的改进。题解 implement-trie-prefix-tree.md 给出的整体空间复杂度为 $O(|T| \times \sum)$，其中 $|T|$ 是所有插入字符串的长度之和，$\sum$ 是字符集大小；
• 空间开销的差异：数组实现中每个节点固定占 26 个槽位，整棵树的最坏空间可膨胀到 $O(d^n)$（$d=26$ 时尤其明显）；哈希表实现只在实际创建子节点时分配空间，稀疏字符集下更省内存，这正是本文选用哈希表实现的直接原因。

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 → 再进阶带.通配 → 再到节点附加数值 / 前缀替换」的顺序练习：

1. 0208. 实现 Trie（前缀树）：Trie 三件套（insert/search/startsWith）的模板题，直接套用本文第 3 节代码即可通过；
2. 0211. 添加与搜索单词 - 数据结构设计：在search中支持.通配符，遇到.时需要递归 DFS遍历当前节点的所有子节点，是 Trie 与深度优先搜索结合的代表题；
3. 0677. 键值映射：在 Trie 节点上附加value字段，sum(prefix)先定位前缀节点，再递归累加子树所有节点的value，对应「前缀统计」应用；
4. 0648. 单词替换：把所有词根插入 Trie，对句子中每个单词沿路径匹配，一旦遇到isEnd即取最短词根替换，对应「字符串检索 + 前缀匹配」应用；
5. 0676. 实现一个魔法字典：构建字典后，枚举searchWord每个位置替换为其余 25 个字母并在 Trie 中查询，注意替换后的字符必须不同于原字符；
6. 1023. 驼峰式匹配：将pattern插入 Trie，匹配查询串时小写字母可跳过、大写字母必须命中，综合考察字符分类与 Trie 匹配。

如需按专题批量刷题，可参考仓库的 字典树题目分类列表，其中整理了完整的 Trie 相关题单。

参考资料

• 【书籍】算法训练营 陈小玉 著
• 【书籍】ACM-ICPC 程序设计系列 算法设计与实现 陈宇 吴昊 主编
• 【开源实现】string_trie.py 字典树 Python 源码（AlgoNote 仓库）
• 【题解】0208. 实现 Trie（前缀树） 等 6 篇字典树专题题解（AlgoNote 仓库）

• 教程
• 文档
• 知识库