Trie树，中文常叫字典树或前缀树，是数据结构里专门为字符串设计的一种树形结构。它最大的特点是利用字符串的公共前缀来节省空间、加速查询，在搜索引擎的搜索提示、拼写检查、敏感词过滤、IP路由的最长前缀匹配等场景中随处可见。很多初学者第一次接触Trie树时，容易被各种指针、children数组绕晕，其实只要抓住它的核心思想，掌握起来并不难。本文将从基本概念讲起，逐步覆盖插入、查找、删除等核心操作，并解答初学者最常见的疑问。
一、Trie树的基本概念与结构原理
Trie树的核心思想非常朴素：把所有字符串按字符逐层拆开，相同前缀的字符串共享同一段路径。举个例子，假设我们有三个单词：cat、car、dog。用这三个单词构建Trie树时，根节点不存任何字符。插入cat，从根节点往下依次建立c、a、t三个节点；插入car时，发现c和a已经存在，直接复用，只需在a下面新建一个r节点；插入dog时，c开头的路径完全对不上，于是从根节点新建d、o、g三个节点。
这样构建出来的树有一个明显特征：从根节点到某个节点的路径上经过的字符连起来，就是一个字符串的前缀。cat和car共享了ca这段路径，这就是公共前缀复用。当字符串数量庞大且前缀重复度高时，这种结构能省下不少存储空间，更重要的是查询效率不会随字符串总量增长而明显下降。
在代码实现上，每个Trie节点通常包含两部分：一是子节点的引用，可以是一个固定大小的数组（比如只处理小写字母时开26个槽位），也可以是一个哈希表（字符种类不确定时更灵活）；二是一个标志位，标记这个节点是否是某个字符串的结尾。为什么要这个标志位？因为如果只存cat和catalog两个词，查cat时走到t节点，但t节点并不是终点，没有标志位就无法区分cat是不是一个完整的词。
二、Trie树的核心操作详解
1. 插入操作
插入一个字符串时，从根节点出发，逐个取出字符。如果当前节点的子节点中已经存在该字符对应的节点，就直接走过去；如果不存在，就新建一个节点挂上去。字符串处理完毕后，把最后到达的节点的结束标志设为true。整个过程的时间复杂度是O(L)，L是字符串长度，与树里已经存了多少字符串无关，这一点比在哈希表里处理冲突、在平衡树里做旋转调整要稳定得多。
2. 查找操作
查找同样从根节点开始，逐字符向下匹配。任何一步发现子节点不存在，说明这个字符串一定不在树中，可以立即返回false。走完所有字符后，还要检查最后节点的结束标志：标志为true，字符串存在；标志为false，说明这个字符串只是别的词的前缀，本身并没有被插入过。比如树里只存了catalog，查cat就会遇到这种情况。
3. 前缀查询
前缀查询是Trie树的看家本领。判断某个前缀是否存在，过程和查找几乎一样，唯一的区别是不需要检查结束标志，只要能沿着前缀的字符一路走到底，就说明树中至少存在一个以它为前缀的词。搜索引擎输入法里的联想提示，就是先做前缀查询找到前缀对应的子树，再遍历这棵子树收集所有完整单词。
三种操作对比
| 操作 | 时间复杂度 | 是否检查结束标志 |
|---|---|---|
| 插入 | O(L) | 结尾节点设为true |
| 查找 | O(L) | 需要检查 |
| 前缀查询 | O(L) | 不需要检查 |
三、Trie树与其他数据结构的对比
和哈希表相比，Trie树在精确查找上并不占优势，哈希表平均O(1)就能完成。但哈希表有个天然短板：无法做前缀查询。你想找出所有以ab开头的词，哈希表只能遍历所有键，而Trie树直接定位到子树即可。此外，哈希表一旦数据量大，冲突增多或需要扩容，性能会抖动，Trie树则始终稳定在O(L)。
和红黑树、跳表这类平衡结构相比，Trie树跳过了字符串逐字符比较的开销。红黑树查找一个字符串需要多次完整比较字符串大小，复杂度还与字符串长度相关，而Trie树每次只消费一个字符。当然，Trie树的代价是空间开销：每个节点都要维护子节点容器，字符集大、前缀重复度低时，空间浪费会比较明显。
四、初学者常见疑问解答
疑问一：Trie树和前缀树是一回事吗？
是的，Trie树、字典树、前缀树、单词查找树指的都是同一个结构。Trie这个名字取自retrieval（检索）的中间部分，读作try或者tree都有人用，不必纠结。
疑问二：内存开销太大怎么办？
如果用固定数组存子节点，比如26个字母开26个槽，大部分槽位是空的，确实浪费。常见的优化方案有三种：一是改用哈希表存子节点，用到才分配空间；二是采用双数组Trie（Double-Array Trie），用两个数组模拟整棵树，空间效率极高，代价是实现复杂；三是在节点里压缩只有单链的路径，类似Radix树（基数树）的思路。
疑问三：中文字符串怎么处理？
Trie树本身不关心字符是什么，它只把字符当作一个键。中文可以按字符逐个处理，每个汉字当作一个键放进哈希表式的节点；也可以先做编码处理，按UTF-8字节或按词切分后再建树。敏感词过滤系统里通常按汉字直接建树，实现简单效果好。
疑问四：删除操作怎么做？
删除比插入和查找稍微麻烦。常用做法是懒惰删除：先查找该字符串，找到后只把结尾节点的标志位改为false，节点本身留着。这样实现最简单，但会积累无用节点。彻底删除则需要递归回溯，删掉只被目标字符串占用的节点，遇到被其他词共享的节点就停止，实现时要小心判断节点是否还有其他子节点或本身是别的词的结尾。
五、学习建议与实践路线
初学阶段建议先用自己熟悉的语言手写一遍Trie树，节点用最简单的数组实现，只处理小写字母，把插入、查找、前缀查询三个接口跑通。LeetCode上的实现Trie（前缀树）题目是绝佳的起点，通过后再挑战单词搜索、添加与搜索单词、单词替换等进阶题。
掌握基础实现后，可以进一步了解AC自动机，它是在Trie树基础上加失败指针构建的多模式匹配算法，能一次性在文本中匹配成千上万个关键词，是敏感词过滤、入侵检测系统的核心。理解了Trie树，AC自动机的学习会顺畅很多。
Trie树的价值不在于替代哈希表做精确查找，而在于前缀相关的问题它是独一无二的解法。先理解公共前缀复用这一个核心思想，剩下的实现细节都是水到渠成。