树系列第 17 篇：Trie——前缀树

本文是”树系列”的第 17 篇。第 3 篇我们认识了二叉树，第 15 篇认识了跳表，第 16 篇认识了堆；今天要见的是多叉树家族里最出名的一位——Trie（前缀树）。它不存数字，也不存通用的键值对，而是专门为字符串而生：把单词按字符拆开，把共享的前缀合并存放。搜索引擎的下拉提示、手机输入法的候选词、IDE 的代码补全、路由器的 IP 匹配，背后都有它的身影。本篇会从”为什么哈希表帮不了前缀查询”讲起，一步步实现插入、查找、删除、词频统计，再聊压缩 Trie 和双数组 Trie，最后用速查表和自测题收尾。

0 先回顾：多叉树长什么样

第 3 篇里我们说过，二叉树的每个节点最多有两个孩子，左孩子和右孩子各司其职。可现实中的”多选一”关系常常超过两个分支：一个目录下面可以有很多子目录，一个组织的老板可以管很多员工，一个网址的域名下面可以挂无数个页面。把”最多两个孩子”放宽成”可以有任意多个孩子”，就得到了多叉树（multi-way tree）。多叉树的定义几乎和二叉树一样：每个节点有一个值，下面挂着若干棵互不相交的子树，根在最上面，孩子之间没有环路。区别仅仅在于”孩子数目的上限”。

Trie 就是多叉树里最经典、最贴近真实使用场景的例子。它的每个节点同样可以有多个孩子，而且孩子的数量通常由字符集决定：如果只存 26 个小写英文字母，每个节点最多 26 个孩子；如果存中英文混合文本，孩子数量就是”你见过多少个不同的字符”。这正是多叉树的威力：分支的维度可以不是”左/右”两个固定位置，而是”a/b/c/……”这样一组有名字的插槽。下面我们就看看，为什么字符串天生适合用这样的树来组织。

1 问题：前缀补全怎么做到

1.1 三个日常场景

先感受一下”前缀查询”到底有多常见。

场景一：搜索引擎。你在搜索框里敲下”结”，还没敲完，浏览器立刻弹出候选：“结构体”、“结对编程”、“结合”。你输入的只是三个字符，候选词却是一长串以”结”开头的词条。这就是前缀补全（prefix completion）。

场景二：手机输入法。输入”shu”，候选区出现”书、树、数、输、属”。拼音输入法做的事情比这复杂一些，但核心之一是：维护一个巨大的”拼音前缀 → 候选汉字/词组”的映射，你每多打一个字母，它就重新筛选一遍候选。

场景三：IDE 代码补全。敲一个对象名和点号，编辑器立刻列出这个对象的所有方法名；敲出 pri，编辑器提示 print、private、priority。IDE 背后是一张成员名/符号名的词典，你的输入就是前缀。

三个场景共享同一个需求：给定一个前缀，快速找出所有以它为开头的字符串。听起来很简单，但数据量上去之后，朴素做法立刻撑不住。

1.2 朴素做法为什么慢

最直接的做法：把词典里所有单词过一遍，逐个判断”是否以输入前缀开头”。

比如词典里有十万个单词，平均每个单词长 8 个字符，用户输入前缀 “pri”。你需要做十万次 startsWith 判断，每次判断最多比较 3 个字符。十万次听起来不算多，但如果把搜索框的每一次按键都算上——用户每敲一个字符，前端就发一次请求，后端就要扫一遍全词典——那就变成”输入长度 × 词典大小 × 平均词长”的乘法。更糟的是，手机输入法每按一次键都要在几毫秒内完成候选刷新，十万单词的词典配上海量用户并发，全表扫描根本扛不住。

图里画的是朴素方法的命运：大部分单词跟你的前缀毫无关系，却要被白白比较一遍。如果能把”以 pri 开头”这件事变成”顺着 pri 这条路径走到底，看看下面还挂着什么”，效率就会完全不同。

1.3 哈希表为什么帮不上忙

有人会想：把单词全部塞进哈希表，查找不都是 O(1) 吗？前缀查询为什么不能直接用哈希表？

关键在于：哈希表解决的是”精确相等”问题，不是”前缀包含”问题。你问哈希表”词典里有没有 private”，它能在常数时间内给你答案；但你问它”有哪些单词以 pri 开头”，它就哑火了。原因有两点。

第一，哈希函数的作用是把键打散。private 和 print 在字典序上挨得很近，但经过哈希函数之后，它们的桶位置几乎没有任何关系——哈希表的设计目标就是让相似的键尽量散开，以便均摊冲突。前缀信息在哈希之前就被抹掉了，你无法从”private 的桶”附近找到”print 的桶”。

第二，要回答前缀查询，哈希表唯一的办法是枚举：把 keys 集合全拿出来，逐个做前缀判断，再收集命中的。这一步的复杂度是 O(N × L)，N 是词典大小，L 是前缀长度——和朴素做法一模一样，之前省下的 O(1) 查询优势荡然无存。而且哈希表本身不维护任何顺序，即使你想做”按字典序补全”，也得先把命中结果排序。

跳表、二叉搜索树这类有序结构比哈希表好一些：它们支持”范围查询”，比如”找出所有在 [pri, prj) 之间的字符串”。听起来很接近前缀查询，但实际上还不够——范围查询要求你有一个明确的上下界，而前缀补全需要的只是”以 pri 开头”，边界是隐式的；更关键的是，范围查询返回的集合里仍然可能混入 prick 这样的词，你需要逐词过滤，或者把上下界设计得极其小心。本质上，有序结构把”找前缀”翻译成了”找范围”，多了一层别扭。

1.4 想要的结构：共享前缀

让我们换一个思路。词典里 cat、car、care 共享前缀 ca。如果每个单词都单独存一份，c 和 a 这两个字符要被复制三遍；如果把它们合并成一条公共路径，c → a 只出现一次，后面再从 a 分叉成 t 和 r。这样一来：

• 判断”ca 是不是前缀”，只需要顺着 c、a 两条边走到那个分叉节点；
• 找出”所有以 ca 开头的词”，只需要看看从分叉节点往下能走到哪些终止位置；
• 单词越多、共享前缀越多，节省的空间和查找时间越明显。

把”字符作为边、前缀作为节点”的树画出来，就是 Trie。从下一节开始，我们正式定义它。

2 Trie 的定义

2.1 三句话定义

Trie 的定义可以浓缩成三句话。

第一句：根节点不保存任何字符，它代表空字符串。为什么根代表空串？因为从根出发，一步都不走，路径上拼出来的字符串就是”什么都没有”。空串是所有单词的共同前缀，把它放在根部再合适不过。

第二句：每条边都标着一个字符，从根走到某个节点的路径上，所有边的字符依次拼接，就是这个节点代表的前缀。也就是说，树里的每个节点都”隐含”了一个字符串——这个字符串由从根到它的那条路径唯一决定。我们平时说的”c 节点”、“ca 节点”，指的就是分别代表前缀 “c”、“ca” 的节点。

第三句：某些节点带有终止标记，表示从根走到这里拼出的字符串是一个完整单词。为什么需要这个标记？因为一个前缀既可以是别的词的开头，也可以自己就是一个词。比如 “car” 是完整单词，同时它又是 “care” 的前缀；如果没有终止标记，我们就分不清”走到 car 节点”到底是”找到了 car 这个词”还是”正在前往 care 的路上”。

把 cat、car、care 三个单词按共享前缀原则画出来，得到下面这棵树。圆圈是节点，圆圈里写的是该节点代表的前缀；边上的字母是”从父亲走到孩子需要吃掉的字符”；带五角星的节点表示这里有一个完整单词结束。

这棵树只有 6 个节点：根、c、ca、cat、car、care。单词 cat、car 共享了 c、ca 两个节点；car 和 care 共享了 c、ca、car 三个节点。如果不用 Trie 而把三个单词原样存进数组，c 和 a 这两个字符总共要出现六次；用 Trie 之后，它们各自只出现一次。共享前缀越多的词典，Trie 的压缩效果越明显。

2.2 几个必须看清的细节

先看 ca 节点。从根走到它，路径上拼出 “ca”，但我们的词典里并没有 “ca” 这个单词，所以它没有终止标记。它存在的意义只是”作为 cat 和 car 的公共走廊”。这告诉我们：不是每个节点都对应一个完整单词，节点对应的是前缀。

再看 car 节点。它带有终止标记，因为 “car” 是词典里的完整单词；同时它还有一个孩子 e，说明 “car” 也是 “care” 的前缀。这个例子引出一条重要结论：叶子节点一定是某个单词的终点，但单词的终点不一定是叶子。判断”走到某个节点是否找到了一个词”，永远要看终止标记，而不是看它有没有孩子。

最后看 cat 和 care 两个节点，它们是叶子，也没有孩子。叶子在这里的含义是：没有比它们更长的、以它们为前缀的单词了。

2.3 节点里到底存什么

一个 Trie 节点最少需要两部分信息。

第一部分是孩子表：从”字符”到”子节点”的映射。实现时有两种主流选择。如果字符集固定且很小，比如只处理 26 个小写英文字母，可以用长度 26 的数组，下标 0 到 25 分别对应 a 到 z，某个位置是空指针就表示”没有走这个字符的孩子”；这样做查找极快，一个下标运算就能定位孩子，但每个节点都要背上 26 个槽位，哪怕大部分槽位是空的。如果字符集很大，比如要处理中文、日文、emoji，或者根本不确定会遇到什么字符，就用哈希表 Map 保存”字符 → 子节点”；这样每个节点只保存实际存在的孩子，内存更省，代价是每次定位孩子要多一次哈希运算。

第二部分是终止标记：一个布尔值 isEnd（有的实现叫 isWord 或 isTerminal），表示从根走到当前节点拼出的字符串是否是一个完整单词。后面讲词频统计时，我们会把布尔值升级成数字计数。

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEnd = false;
}

这里用 Map 实现孩子表，是为了让代码在任意字符集下都能工作；如果你确定只处理小写英文，把 children 换成 TrieNode[] 数组、长度 26，逻辑完全一样。

2.4 为什么它叫”前缀树”

“Trie” 这个词来自英文 retrieval（检索）中间的几个字母，中文习惯叫前缀树，因为它和前缀之间存在一个精确的一一对应关系：树里的任何一个节点，都恰好对应词典中某个字符串的一个前缀；反过来，从根出发的任意一条路径，也都对应一个前缀。

以 {cat, car, care} 为例，所有单词的全部前缀是：空串、c、ca、cat、car、care，一共六个，恰好和上图六个节点一一对应。这个性质非常漂亮：问”词典里有哪些前缀”，等价于问”树里有哪些节点”；问”某个字符串是不是某个词的前缀”，等价于问”从根能不能沿着这条路径走到底”。把字符串集合的组织问题，转化成了树的走路问题，这就是 Trie 的核心思想。

顺带一提，二叉搜索树靠”每个节点左边小、右边大”来组织数据，比较的是节点值的大小；Trie 则完全不做大小比较，它靠的是”孩子有名字”——每个孩子对应一个字符，走到哪一步由输入字符串说了算。这正是第 3 篇里讲的多叉树思想：孩子不叫左孩子、右孩子，而叫 a 孩子、b 孩子、c 孩子。

2.5 空字符串怎么办

一个容易被忽略的边界情况：词典里可能包含空字符串吗？语法上完全可以，某些场景（比如把空输入也当作合法词）确实需要。处理办法很简单：让根节点的 isEnd 为 true。因为根代表空串，根的终止标记为真，就意味着”空串是词典里的一个完整单词”。search("") 就会返回 true，startsWith("") 也会返回 true——毕竟空串是任何字符串的前缀。大多数真实应用不需要空词，但实现时把这条边界想清楚，可以避免很多莫名其妙的 bug。

2.6 一个常见的实现困惑

画图时，字符常常写在边上；写代码时，有人却喜欢把字符存进节点里。这两种做法等价吗？等价，只是视角不同。把字符存在边上，“节点代表的前缀”由路径决定，节点本身不需要额外字段；把字符存在节点里，每个节点会多存一个字符，相当于把边的信息挪了个位置。本文统一采用”边存字符、节点隐含前缀”的经典模型，这样和大多数教科书、以及本系列前面几篇的树图风格一致。后面所有代码也按这个模型实现：孩子 Map 的键就是边上的字符，走到哪个孩子，就等于吃掉哪个字符。

3 插入：逐字符走，没有就建

3.1 插入算法只有三步

Trie 的插入算法简单到可以用一句话概括：从根出发，一个字符一个字符地走；有对应的孩子就顺着走，没有就新建一个孩子再走；把整个单词走完后，在最后的节点打上终止标记。

拆成伪代码就是：

1. 令当前节点等于根节点；
2. 遍历单词的每一个字符：如果当前节点没有”以这个字符为标签”的孩子，就新建一个节点并挂上去；然后移动到该孩子；
3. 循环结束后，把当前节点（也就是最后一个字符对应的节点）的 isEnd 设为 true。

为什么最后一个字符的节点要打标记，而不是第一个、第二个字符的节点打标记？因为 cat 的终点在 t 上。如果走到 c 就标记，词典就会声称 “c” 是一个完整单词；如果走到 a 就标记，词典就会声称 “ca” 是一个完整单词。只有走完整个单词，路径才代表完整的 cat。这个细节是新手写 Trie 最容易犯的错误之一：单词确实插入成功了，结构也画对了，但查的时候永远返回 false，原因就是忘了最后一步标记。

3.2 分步走查：从空树插入 cat

假设词典一开始是空的，树里只有根节点。现在插入 cat，全程需要新建 c、a、t 三个节点。

每一步的”没有就建、建完就走”，最终生成一条从根到 t 的路径：根 —c→ c —a→ ca —t→ cat。注意，这里的节点名 c、ca、cat 是我们为了讲解给它起的”别名”，代码里节点本身并不存这个字符串，它由路径隐含。

3.3 再插入 car：共享走廊不重建

现在往同一棵 Trie 里插入 car。从根出发，处理第一个字符 c：根已经有 c 孩子了，直接走过去，不新建。处理 a：c 节点已经有 a 孩子了，同样直接走过去。处理 r：走到 ca 节点时，发现它没有 r 孩子，于是新建一个 r 节点，走过去，然后标记。

这次插入全程只新建了 1 个节点。对比第一次插入 cat 时新建的 3 个节点，区别就在于 c、a 这段公共前缀已经存在了。Trie 的灵魂就是”共享”：已经走过的路绝不重复修建，只在需要分叉或者需要延伸的地方新建节点。

3.4 最后插入 care：在 car 后面接尾巴

再插入 care。c、a、r 全部存在，顺着走到 car 节点；最后一个字符 e 不存在，新建 e 节点并标记。

现在整棵树的形状就是第 2 节定义图的样子：cat 和 car 在 ca 处分叉，care 是 car 的孩子。三次插入，一共只新建了 5 个节点（c、a、t、r、e），而三个单词的总字符数是 10。也就是说，Trie 用 5 个节点表达了 10 个字符的信息，省下的部分全部来自共享前缀。词典越像”亲戚”（共享前缀越多），压缩比就越高；反之，如果单词之间完全没有共享前缀，比如 abc、def、ghi，Trie 会退化成三条互不相干的链，每个节点只有一个孩子，空间上就不划算了——这个问题正是后面压缩 Trie 要解决的。

3.5 插入已经存在的单词

如果插入的单词本来就在词典里，比如再插一次 cat，会发生什么？从根走到 cat 的路径全都存在，一个节点也不会新建；最后一步只是把 cat 节点的 isEnd 再设一次 true（它本来就是 true）。所以重复插入在结构上是幂等的：第二次插入不会把树变成两份，也不会产生重复路径。

那”重复插入”是不是就毫无意义？分语义看。如果 Trie 只表示”集合”（一个词在不在词典里），重复插入确实无意义；但如果 Trie 表示”多重集”（一个词出现多少次，比如统计用户搜索历史），重复插入就要让计数加一。这一点在第 6 节词频统计里会展开。现在请先记住：结构层重复插入无副作用，语义层是否计数由你决定。

3.6 完整代码

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEnd = false;
}

class Trie {
  private root = new TrieNode();

  insert(word: string): void {
    let cur = this.root;
    for (const ch of word) {
      if (!cur.children.has(ch)) {
        cur.children.set(ch, new TrieNode());
      }
      cur = cur.children.get(ch)!;
    }
    cur.isEnd = true;
  }
}

代码和算法完全一一对应：cur 是”当前节点”，for 循环是”逐字符走”，has 判断是”有没有这个孩子”，set 是”没有就新建”，循环后的 isEnd = true 是”打终止标记”。如果你想把 Trie 泛化成”任意字符的字典树”，这 13 行已经足够；后面几节的所有操作都建立在这棵树的骨架上。

3.7 插入的复杂度

插入一个长度为 L 的单词，循环执行 L 次，每次只做一次 Map 查找和可能的节点创建，时间复杂度是 O(L)。注意，这个复杂度与词典里已经有多少个单词 N 完全无关：插入 international 和插入 a，字典里有一万个词还是一亿个词，走的步数都不变，只看单词本身的长度。这是 Trie 最迷人的性质之一——复杂度由输入字符串长度决定，而不是由数据规模决定。

空间方面，最坏情况下单词的每个字符都要新建一个节点（路径上完全无共享），新增空间 O(L)；最好情况下整条路径都共享，只需要新建很少的节点。整体上，整棵 Trie 的节点数不超过”所有单词总字符数 + 1”，因为每个字符最多对应一次节点创建，而共享前缀只会让这个上限变得更小。

3.8 新手最容易踩的四个坑

第一个坑：忘记在循环结束后标记 isEnd。后果是单词插进去了，search 却永远找不到它。第二个坑：字符集不一致。插入时用大写 ‘C’，查找时用小写 ‘c’，Trie 会认为这是两个完全不同的孩子；处理前统一小写或统一原样保存。第三个坑：把终止标记打在了中途。比如在循环里每个节点都标记一次，词典会凭空多出一堆”前缀词”。第四个坑：插入空字符串。for 循环一次都不执行，cur 始终是根，所以要单独处理”空词 = 根标记”的语义，否则空词会悄悄变成”未插入”。

4 查找：完整词与前缀是两件事

4.1 两种查询，两个答案

Trie 最常用的查询有两种，它们的区别必须一开始就分清。

第一种是完整词查询（search）：问”词典里有没有 cat 这个词”。答案要求两件事同时成立：从根沿着 c、a、t 能走到一个节点，并且这个节点带终止标记。走得到但没标记，说明 cat 只是某个更长词的前缀，不是独立单词。

第二种是前缀查询（startsWith）：问”词典里有没有以 ca 开头的词”。答案只要求一件事：从根沿着 c、a 能走到一个节点。至于这个节点是不是词，根本无所谓——ca 本身不是词，但它是 cat 的前缀，所以 startsWith("ca") 必须返回 true。

用一句话概括：search 要求”走得到，并且是终点”；startsWith 只要求”走得到”。很多面试题故意在这两个方法上挖坑：实现 startsWith 时把 isEnd 也检查一遍，就会漏掉”前缀本身不是词”的合法情况；实现 search 时不检查 isEnd，就会把”是别人的前缀”误判成”是完整词”。

4.2 找不到的两种情况

在 Trie 里查找，找不到一共有两种情况，必须分开理解。

情况一：路径中断。词典里有 cat、car、care，你想查 cap。沿着 c、a 走到 ca 节点后，发现它没有 p 这个孩子——路在这里断了。此时 search("cap") 是 false，startsWith("cap") 也是 false，因为连 cap 这个前缀本身都不存在于词典里。

情况二：路径存在，但节点不是词。你想查 ca。路径 c、a 完全存在，但 ca 节点没有终止标记。此时 search("ca") 是 false（ca 不是词典里的完整词），startsWith("ca") 却是 true（ca 确实是 cat、car、care 的共同前缀）。

这两种情况在代码里的表现也不同：情况一在走路过程中就返回 null，走不到底；情况二走到了底，但终点节点的 isEnd 为 false。下面这张图把三条查询路径同时画出来，方便对照。

4.3 实现代码

两个查询方法共享同一段”沿路径走到底”的逻辑，所以先抽出一个私有方法 findNode：给定字符串，沿着 Trie 一路走，走到底返回终点节点；中途发现孩子不存在，返回 null。

class Trie {
  private root = new TrieNode();

  private findNode(s: string): TrieNode | null {
    let cur = this.root;
    for (const ch of s) {
      const next = cur.children.get(ch);
      if (!next) return null;   // 情况一：路径中断
      cur = next;
    }
    return cur;                 // 走到底，终点可能是词也可能只是前缀
  }

  search(word: string): boolean {
    const node = this.findNode(word);
    return node !== null && node.isEnd;   // 走得到 + 是词
  }

  startsWith(prefix: string): boolean {
    return this.findNode(prefix) !== null; // 只要求走得到
  }
}

findNode 返回 null 表示路径中断；返回节点表示路径存在。search 在节点存在的基础上再加一道 isEnd 检查，startsWith 则到此为止。两个方法一共没几行，但每一种返回值都对应着前面讲的语义，写完后建议自己把 ca、cat、cap 三个输入各走一遍。

4.4 复杂度

完整词查询要比较 L 个字符（L 是单词长度），前缀查询要比较前缀长度个字符，所以两者的时间复杂度都是 O(L)。和插入一样，这个复杂度与词典规模 N 无关。想想第 1 节里那个十万词的例子：哈希表做前缀查询要枚举十万个键，Trie 却只需要走前缀那三五个字符，差距一目了然。

4.5 查询在实际里怎么用

search 的典型场景是精确判词：拼写检查器判断用户输入的单词在不在词典里；数据库判断一个用户名是否已注册；分词器判断一个连续字符串是否是一个合法词。这些都是”是或否”的问题，Trie 给的是确定的布尔答案，而且不依赖词典大小。

startsWith 的典型场景是自动补全的第一步：用户输入 pri，先调用 startsWith("pri") 确认存在以它开头的词，再走到 pri 对应的节点，往下收集所有带终止标记的后代。收集的过程叫”遍历子树”，第 6 节讲词频统计时会给出完整实现。这里先记住分工：startsWith 负责”找到前缀节点”，子树遍历负责”把候选词捞出来”。

4.6 边界情况再检查一遍

search("")：findNode("") 不执行循环，直接返回根。所以 search("") 返回 root.isEnd——这正好呼应第 2 节的约定：只有插入空词并把根标记了，空串才算词。startsWith("") 同样直接返回根节点存在，即 true，因为空串是任何字符串的前缀，只要树不为空（甚至树为空也成立，因为根永远存在），前缀查询永远应该放行空串。

还要提醒一点：如果 Trie 被设计成”不区分大小写”，插入时做了 toLowerCase()，那么查找时也必须做同样的转换，否则 search("Cat") 和 search("cat") 会走向完全不同的分支。统一入口做归一化，比在每个方法里各改一遍要安全得多。

5 删除：小心共享前缀

5.1 删除为什么比插入麻烦

插入和查找都是”顺着路径走”，但删除必须回答一个反方向的问题：路径上的哪些节点可以拆掉？ Trie 的节点几乎都带着”共享”的使命：一个节点可能同时是几个单词的公共前缀，也可能自己就是一个单词的终点，同时还当着更长单词的走廊。随便删一个节点，轻则让别的单词失去路径，重则让整棵子树从根上掉下来。

好在删除规则并不复杂，只需要记住一条总原则：只删除”独享的尾巴”，保留一切公共部分。所谓独享，是指这条路径上没有任何别的单词依赖它；所谓公共，是指某个节点还被其他单词使用。具体到代码，判断依据就两个：节点是不是某个词的终点（isEnd），节点还有没有孩子。

5.2 三种情况逐一拆解

情况一：要删除的词是别的词的前缀。假设词典里有 cat 和 cats。删除 cat 时，cat 节点下面还挂着 s 孩子，cats 还需要这条路径。此时我们能做的只是把 cat 节点的终止标记擦掉：cat 不再是完整词，但节点必须保留。如果手一抖把 cat 节点整个删掉，cats 立刻变成残废——它的路径从 c、a、t 这里断掉了。

情况二：要删除的词的终点有孩子。这和情况一本质相同，只是站在更长单词的角度看。词典里有 car 和 care，删除 car：car 节点下面挂着 e 孩子，所以只擦 car 的终止标记，节点保留，care 毫发无损。

情况三：要删除的词是一条独享的尾巴。词典里有 cat、car、care，删除 care。care 的终点 e 是叶子，没有孩子；从 e 往上看，car 节点还带着 e 这个独享孩子（car 自己同时是词，但它还有 cat 这个兄弟分支？不对，car 的父节点 ca 有两个孩子 t、r，是公共分叉点）。正确的删除流程是：擦掉 e 的终止标记，e 变成”既不是词又没有孩子”的空壳，于是删除 e；回到 car 节点，它现在没有孩子了，但 isEnd 为 true（car 还是词），所以 car 必须保留；再往上走到 ca，ca 还有 t 孩子，自然保留。最终被删掉的只有 e 一个节点。

下面两张图展示删除 care 前后的对比。

再看另一种情况：词典是 cat 和 cats，删除 cat。此时 cat 节点是 cats 的必经之路，绝不能删，只能擦掉它的终止标记。

对照两张图可以发现，删除操作真正在问的问题永远是：擦掉标记之后，这个节点还能不能继续活下去？ 只要它 isEnd 为 true 或者还有孩子，它就必须活着；只有当它既不是词、又没有孩子，才轮到”把它从父亲的 children 里移除”这一步。

5.3 递归删除的实现

删除天然适合用递归写：先递归到最底层的终点节点处理标记，再沿着原路返回，逐层决定”上面的节点要不要删”。

class Trie {
  private root = new TrieNode();

  deleteWord(word: string): boolean {
    return this.remove(this.root, word, 0);
  }

  // 返回 true 表示当前节点可以被删除（不是词终点，也没有孩子）
  private remove(node: TrieNode, word: string, depth: number): boolean {
    if (depth === word.length) {
      if (!node.isEnd) return false;   // 这个词本来就不存在
      node.isEnd = false;              // 先擦掉终止标记
      return node.children.size === 0; // 没有孩子才可能被删
    }

    const ch = word[depth];
    const child = node.children.get(ch);
    if (!child) return false;          // 路径中断，词不存在

    const shouldDeleteChild = this.remove(child, word, depth + 1);
    if (shouldDeleteChild) {
      node.children.delete(ch);        // 独享的尾巴，拆掉
    }

    // 自己既不是词、又没孩子了，才允许被上层继续拆
    return node.children.size === 0 && !node.isEnd;
  }
}

代码的核心是 remove 的返回值：它告诉父节点”我这个节点是不是已经没用了”。递归到底部时，先处理 isEnd——如果是 false，说明单词根本不存在，直接返回 false；如果是 true，擦掉标记，然后看自己有没有孩子。回溯到中间层时，如果子节点报告”我可以被删”，就把那条边从 children 里移除；最后判断自己能不能继续被删，标准就是”没孩子且不是词终点”。根节点永远不会被删除：即使 remove 在根上返回 true，也没有父亲来执行 delete。

5.4 复杂度与注意事项

删除一个长度为 L 的单词，递归最多深入 L 层，每层做常数次操作，时间复杂度 O(L)。空间上，递归栈深度也是 O(L)，如果担心长字符串的栈开销，可以改成迭代版，但逻辑会绕一些，一般场景递归足够。

三个容易出错的细节。第一，删除不存在的词：remove 会在中途遇到路径中断或终点 isEnd 为 false，返回 false，不会误伤任何节点，所以实现里不需要先 search 一遍；当然先 search 也无妨，只是多一次 O(L) 的遍历。第二，重复删除：第一次删除成功后，isEnd 已经是 false，第二次删除同一个词会返回 false，这是正确行为。第三，别忘了空词：删除空串要直接操作根节点，把它视为”根不是词终点”即可，不要试图递归进任何孩子。

5.5 偷懒方案：惰性删除

有些场景根本不需要真正释放节点。比如自动补全的候选词字典几乎只增不减，偶尔删除个别敏感词，此时可以采用惰性删除：只把终点节点的 isEnd 置为 false，路径上的节点原封不动保留。好处是删除 O(L) 且代码极简，后续再插入这个词时还能复用路径；坏处是”曾经存在过”的节点会一直占着内存，如果词典增删非常频繁、规模又大，内存会成为问题。真实系统里，权衡”结构删除的复杂代码”和”惰性删除的内存开销”，往往比想象中更常选后者——尤其是当词典大部分时间是只读的、只有少量删除时。

6 词频统计：让补全知道谁更热门

6.1 光有词典还不够，还要有热度

自动补全的雏形我们已经有了：startsWith 找到前缀节点，再遍历子树收集候选词。但真实的搜索框和输入法不会把所有候选按字典序平铺给你——它们会把最热门的词排在最前面。用户在搜索框输入”结”，期望看到”结构体、结合、结婚”，而不是”结巴、结冰、结党”。这些顺序不是凭空来的，而是统计了成千上万次真实搜索后得到的词频。

于是 Trie 需要从”集合”升级成”带计数的多重集”：同一个词可以插入很多次，每插入一次，它对应的统计数字就加一。实现上只需要在节点里加两个计数，就能同时支持”这个词有多热”和”这个前缀下总共有多少热度”两种查询。

6.2 两种计数：endCount 和 passCount

第一种叫 endCount（终点计数），记在单词终点节点上，表示”这个词作为完整词出现了多少次”。插入 cat 五次，cat 节点的 endCount 就是 5。它回答的问题是：给定一个完整单词，它出现过多少次？

第二种叫 passCount（经过计数），记在路径上的每一个节点，表示”有多少次插入从当前节点经过”。插入 cat 五次、car 三次、care 两次，那么根节点、c 节点、ca 节点的 passCount 都是 10；car 节点的 passCount 是 5（car 自身 3 次加上经过它到达 care 的 2 次）；cat 节点的 passCount 是 5。它回答的问题是：给定一个前缀，词典里所有以它为开头的词一共被命中过多少次？

图里每个节点标注了它的计数：end 表示以该节点结尾的完整词出现次数，pass 表示经过该节点的插入次数。注意 car 节点：end 是 3，pass 是 5，两个数字不相等，正是因为它既是自己的终点，又是 care 的走廊。这张图说明了一个重要事实：passCount 沿路径向上累加，根节点的 passCount 等于历史插入总次数。

6.3 带计数的插入

把第 3 节的插入稍微改一下：每走一步，当前节点的 passCount 加一；走到终点后，终点节点的 passCount 和 endCount 都加一。

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  endCount = 0;   // 这个词作为完整词出现的次数
  passCount = 0;  // 经过这个节点的插入次数
}

class Trie {
  private root = new TrieNode();

  insert(word: string): void {
    let cur = this.root;
    cur.passCount++;
    for (const ch of word) {
      if (!cur.children.has(ch)) {
        cur.children.set(ch, new TrieNode());
      }
      cur = cur.children.get(ch)!;
      cur.passCount++;
    }
    cur.endCount++;
  }

  frequency(word: string): number {
    let cur = this.root;
    for (const ch of word) {
      const next = cur.children.get(ch);
      if (!next) return 0;
      cur = next;
    }
    return cur.endCount;
  }
}

insert 里 root.passCount++ 不能省：根代表空前缀，任何一次插入都从根经过。frequency 和 search 几乎一样，只是返回计数而不是布尔值。此时 isEnd 其实可以被 endCount > 0 取代：endCount 大于零就说明这个词存在，省掉一个布尔字段，逻辑反而更统一。

6.4 前缀热度与候选排序

有了计数，前缀查询就变成了除法：以前缀 p 开头的插入占总插入的”热度比例”是多少？答案是 passCount(prefix) / passCount(root)。比如上图里根节点 pass=10，ca 的 pass=10，说明所有历史插入都以 ca 开头——这是当然的，因为词典只有三个词且都共享这个前缀。如果用户输入一个冷门前缀，它的 passCount 会很小，系统可以据此判断”这个前缀没有足够候选”，提前降级为”无建议”。

真正把候选按热度排序，需要做三步：第一步，用 startsWith 走到前缀节点；第二步，从该节点开始深度优先遍历整棵子树，收集所有 endCount > 0 的节点，同时用沿途字符拼出完整单词；第三步，按 endCount 从大到小排序，取前 K 个作为补全结果。

function collect(node: TrieNode, prefix: string, out: { word: string; freq: number }[]) {
  if (node.endCount > 0) {
    out.push({ word: prefix, freq: node.endCount });
  }
  for (const [ch, child] of node.children) {
    collect(child, prefix + ch, out);
  }
}

这个收集函数是自动补全的发动机：递归进入每个孩子时，把当前路径字符串拼上边的字符，遇到 endCount > 0 的节点就记下一个候选。收集完成后按频次排序即可。注意它的时间复杂度与”前缀子树里的节点数”成正比——如果某个前缀下面挂了十万个词，排序就要花十万量级的时间。为了更快，真实系统会在节点里缓存”本子树最热门的 Top K”列表，插入时沿途更新；这样查询时直接读缓存，复杂度降到 O(K)。这就是搜索引擎”毫秒级联想”背后的常用招数。

6.5 从词频到输入法

拼音输入法的候选排序比这复杂，但骨架一样：每个”拼音前缀”是一棵 Trie，叶子挂着候选汉字或词组，每个候选带着语言模型给的分数（等价于频次）。你输入 “shu”，系统走到 shu 节点，把子树里分数最高的候选捞出来，再按分数排序。搜索热词榜同理：把用户每一次点击搜索词当成一次插入，endCount 就是这个词的热度，按热度排榜就是现成的 Top K 问题。

6.6 带计数的删除

如果支持删除，计数版 Trie 的删除要同时维护两个计数器：沿路径把 passCount 减一，终点把 endCount 减一。惰性删除在这里特别自然：endCount 归零就等价于”这个词不存在”，结构节点可以留着复用。判断”词是否存在”也从 isEnd 变成了 endCount > 0。一句话总结计数删除的语义：删除减的是数字，不是结构；结构是否回收，是另一层独立的决策。

7 复杂度：为什么它和数据量无关

7.1 时间：永远只看字符串长度

Trie 的四个核心操作——插入、完整词查找、前缀查找、删除——时间复杂度全都是 O(L)，其中 L 是参与操作的字符串长度。这个结论值得反复强调：它和词典里已经存了多少个词 N 完全无关。一百万词的词典和一亿词的词典，插入同一个 hello 花的步数一模一样，都是 5 步（最多再算上每步的哈希查找）。原因在第 3 节已经埋下：Trie 每一步只关心”当前节点有没有以这个字符为标签的孩子”，这个信息被组织在节点内部，不需要和别的单词比较，也不需要扫描全局。

对比一下：朴素做法做一次前缀查询要 O(N × L)，哈希表做前缀查询同样要枚举所有键 O(N × L)，二叉搜索树做范围查询要 O(log N + 命中数)。在”前缀查询”这个赛道上，Trie 的 O(L) 是断崖式的领先，这也是它在字符串领域不可替代的根本原因。

有人会抬杠：哈希表的精确查找是 O(1)，Trie 的查找是 O(L)，岂不是哈希表更快？这里有个容易被忽略的细节：哈希表计算哈希值本身也要读一遍整个字符串。hash("hello") 这个操作通常就要 O(L) 时间（除非把哈希值缓存起来，而缓存的代价是每个字符串多存一个数字）。所以公平地说，哈希表的”O(1)“是”哈希值算好之后”的 O(1)，把算哈希的代价算进去，精确查找也是 O(L)。Trie 和哈希表在”必须读完整输入”这件事上并没有本质差别，差别在于哈希表拿到哈希值之后只有桶位置，而 Trie 拿到的是一个可以继续走下去的节点。

7.2 空间：两个开销来源

空间复杂度要分两部分看。第一部分是节点本身的数量：把 N 个单词插入 Trie，节点数最多不超过”所有单词总字符数 + 1”，因为每个字符最多触发一次节点创建，而共享前缀会让实际节点数明显小于这个上限。用 S 表示所有单词的总字符数，节点数就是 O(S)。

第二部分是每个节点的孩子表开销，这里有两种实现，代价天差地别。

如果字符集固定为 26 个小写字母，用定长数组存孩子，那么每个节点固定占 26 个槽位，总空间是 O(S × 26)。当 S 是千万级别时，26 倍就是两亿多个引用，即使大部分槽位为空，内存也照付。好处是访问孩子不用哈希，一个下标运算搞定，速度快。

如果字符集不确定（中文、emoji、多语言），用 Map 存孩子，那么每个节点只保存实际存在的孩子，总边数恰好等于非根节点数，空间是 O(S)。代价是每次定位孩子要算一次哈希。真实系统里，纯英文小写词典常用数组，多语言和中文词典几乎必选 Map。

上图把两种方案的前缀查询路线放在一起：Trie 是”走到前缀节点再看下面有什么”，哈希表是”把所有键翻出来逐个问”。路线长短的差别，就是 O(L) 与 O(N × L) 的差别。

7.3 有序性：Trie 的隐藏技能

哈希表为了散列，把键的顺序彻底打乱；而 Trie 天然有序。只要按孩子 Map 的键顺序（对数组版就是下标 0 到 25）做深度优先遍历，输出的所有完整单词就恰好是字典序。为什么？因为字典序的定义就是”从第一个字符开始逐位比较”，而 Trie 的第一层已经按第一个字符分组，第二层按第二个字符分组，依此类推。DFS 先走小的字符、再走大的字符，出来的顺序自然和字典序一致。

这个性质在”按字典序输出所有词”、“找词典中某单词的后继前驱”、“实现字符串排序”等场景里非常值钱。哈希表想做到这一点，只能先把所有键捞出来排序，多付一次 O(S log S) 的代价。

7.4 与哈希表的正面对决

把上面所有结论收进一张表：

维度	Trie	哈希表
精确查找	O(L)，稳定	O(1) 平均，冲突时退化
前缀查询	O(L)，直接支持	不支持，需枚举 O(N × L)
有序输出	天然字典序	无序
插入	O(L)	O(1) 平均
删除	O(L)	O(1) 平均
空间	共享前缀压缩，孩子表有开销	存完整键，还要留桶
最坏情况	稳定，无退化	哈希冲突可退化为 O(N)
适用场景	字符串词典、前缀、补全	通用键值对、精确存取

7.5 怎么选：不是取代，是分工

这张表不是要宣判哈希表死刑。恰恰相反，哈希表是通用键值存储里最优秀的选手之一：缓存、字典、去重、索引，全是它的主场。Trie 的舞台很窄，但在这个舞台上是绝对的王者：只要需求里出现”前缀”两个字，哈希表就出局。前缀查询、自动补全、词频联想、IP 最长前缀匹配，这些需求 Trie 是教科书答案。

如果需求是”字符串精确判重”呢？两者都能做：哈希表快且省，Trie 稳定且顺便支持前缀。实际工程里，很多拼写检查器确实用哈希集合存词典，因为只需要精确判词；而搜索引擎的联想、输入法的候选，一定用 Trie 或它的变体。选择的标准很简单：问自己一句——我将来会不会问”以什么开头”？ 会，就用 Trie；永远只问”在不在”，哈希表就够了。

8 变体与应用：从字典树到工业界

8.1 压缩 Trie：把单行道合并成一条边

普通 Trie 有一个明显的浪费：单子节点长链。如果词典里恰好有一批共享长前缀的单词，比如 bat、batch、battery，那么 b、a、t 三个节点共享没问题；可如果某个分支从头到尾只有一个孩子，比如到达 t 之后通向 batch 的 c、h 两个节点，每个节点都只有一个孩子，却各自要占一个节点、一张孩子表，就很不划算。

请看下面这棵普通 Trie 的形状。实线是共享主干，虚线框里全是”只有一个孩子的中间节点”，它们只承担”把路引向终点”这一个职责。

普通 Trie 里，从 t 到 batch 的终点要新建 c、h 两个只有单一孩子的节点；从 t 到 battery 的终点要新建 t、e、r、y 四个。**压缩 Trie（compressed Trie，也叫 Radix Tree 基数树、Patricia 树）**的做法是：把这种”只有一个孩子、自己又不是词终点”的连续路径合并成一条边，边的标签从单个字符变成一段字符串。合并之后，上面 12 个节点的树缩成了 4 个节点：根、bat、ch、tery。

8.2 压缩的规则

压缩 Trie 里哪些节点必须保留？三条规则。第一，根必须保留。第二，单词终点必须保留——bat 节点虽然只有一个孩子，但它是完整词，不能并入边里，否则”bat 是词”这个信息会丢失。第三，分支点必须保留——bat 之后的 ch 和 tery 分道扬镳，这里必须有节点分叉。

反过来，只有一种节点会被合并掉：既不是词终点、又只有一个孩子的节点。它只是走廊，合并成边标签后信息一点不少。你可能会问：合并后怎么知道 ch 是单词而不是前缀？压缩 Trie 照样用终止标记：ch 节点标记为词，tery 节点标记为词，而 bat 既是词又是分叉点，它的标记独立存在。所有语义规则和普通 Trie 完全一致，变的只是”边能走多长”。

8.3 插入时的边分裂

压缩 Trie 的插入比普通 Trie 多一个动作：边分裂（edge splitting）。假设当前树里已经有一条从根出发、标签为 battery 的边直达终点，现在要插入 bat。沿边比较时，bat 与 battery 共享前三个字符，但 bat 在第三个字符后就结束了，边还有 tery 没走完。此时必须把边 battery 劈成两段：先建一个 bat 节点，它既是 bat 的终点，也是通往剩余边的分叉点；原边剩下的一截 tery 挂到 bat 节点下面。

分裂之后的形状正是上面右图：根 —“bat”— bat★，bat 下面挂着 “tery” 和 “ch” 两条边。如果插入的新词和已有边只有部分前缀相同，同理：把边从”分歧点”剪开，公共部分保留为边，剩余部分各走各路。分裂操作让压缩 Trie 的插入不再”只加一个节点”，但均摊代价依然是 O(L)（L 是字符串长度），只是常数比普通 Trie 大一些。

8.4 查找与删除

压缩 Trie 的查找不再逐字符走，而是逐边比较：从根开始，看输入字符串与当前边的标签能匹配多长。如果匹配长度小于标签长度，说明输入在这个节点内部就断了，直接失败；如果正好匹配完一条边，就走到边的终点继续。整体时间仍是 O(L)，因为每条边的标签最终都要被输入字符串”消化”。

删除则是压缩 Trie 最麻烦的部分：删掉一个词后，可能让某个节点的孩子数从 2 变成 1，此时理论上有机会把”单子路径”重新合并回一条边。很多实现图省事，选择不立即重新压缩——反正压缩与否不影响正确性，只影响空间。工程上的取舍和普通 Trie 的惰性删除一脉相承：正确性永远优先，优化可以后补。

8.5 什么时候压缩收益最大

压缩 Trie 不是银弹。它的收益来自”长单链”：单词很长、分支很少、共享前缀很长的词典，比如 IP 地址、URL、DNA 片段、命名空间路径，压缩效果立竿见影。反过来，如果词典全是短单词且分叉密集，比如英文常见词 a、an、and、any，节点本来就都靠前分叉，压缩能合并的部分很少，收益有限，还要付出边分裂的复杂度。所以真实系统里，普通 Trie 与压缩 Trie 都有用武之地：搜索引擎联想词库短而密集，普通 Trie 就够；路由表和文件系统路径长而稀疏，Radix Tree 更合适。

8.6 双数组 Trie：把树压进数组

无论是 Map 还是数组孩子表，普通 Trie 的每个节点都是一个独立对象，散落在内存里，指针跳来跳去，缓存很不友好。对于上亿条目的静态词典（比如输入法的词库、中文分词的词表），这个开销会被放大到难以接受。双数组 Trie（Double-Array Trie） 给出了一个极端方案：用两个整型数组 base 和 check 表示整棵树，不存任何指针。

原理一句话：把每个节点编号成数组下标，转移状态时用 base[s] + c 算出下一个状态的下标，再用 check 数组验证这个转移是否合法。base 负责”算路”，check 负责”验票”，双数组的名字就是这么来的。它的优点是状态转移 O(1)、内存连续、无指针解引用，速度极快；缺点是构建过程非常复杂，而且要预先知道全部词（或者支持很麻烦的动态插入），所以它几乎总是用于只读的大型静态词典。经典的 AC 自动机、中文分词器、输入法词库索引里，双数组 Trie 是常见的地基。

8.7 后缀树：Trie 家族的下一位明星

这里必须提一个亲戚：后缀树（suffix tree）。把一个字符串的所有后缀——banana、anana、nana、ana、na、a——全部插进一棵 Trie，再按压缩 Trie 的方式合并单子路径，得到的树就叫后缀树。它把”字符串里有没有子串 X”变成”从根能不能沿着 X 走到某个节点”的问题，还能在线性时间内回答最长重复子串、最长公共子串等经典难题。后缀树是字符串匹配系列的重量级嘉宾，本篇不展开，只预告：前缀树是”单词集合”的索引，后缀树是”单个字符串”的索引。想先动手感受子串与匹配算法的，可以直接去第 9 节提到的串匹配实验室玩一玩。

8.8 应用一：IP 路由的最长前缀匹配

互联网路由器每秒要处理海量数据包，每个包都带着目标 IP。路由表里不是”某个 IP 对应某条出口”这种精确匹配，而是”某个前缀对应某条路由”，比如 192.168.0.0/16 表示前 16 位匹配的所有地址都走这条线。问题来了：一个目标 IP 可能同时匹配多个前缀，比如 192.168.1.200 既匹配 192.168.0.0/16，也匹配 192.168.1.0/24，还匹配 192.168.1.128/25。路由器必须选择掩码最长、最具体的那条——这就是最长前缀匹配（Longest Prefix Match, LPM）。

把 IP 看成二进制字符串，路由表就是一棵按位分叉的 Trie：每条边是 0 或 1，每个路由前缀是一个带标记的节点。查找目标 IP 时从根沿位走下去，沿途遇到的每一个”路由节点”都是候选，但只保留深度最大（掩码最长）的那个。这种”走到底、记住最深”的策略，正是 Trie 前缀查询在真实网络世界里的经典应用。软件路由器和转发表常用 Radix Tree 实现，硬件交换芯片则用更专门的 TCAM，但思想同源。

8.9 应用二三四：补全、拼写、敏感词

自动补全我们已经聊了很多：搜索框、IDE、命令行、数据库名提示，都是”前缀节点 + 子树收集 + 词频排序”三步曲。加上第 6 节的 Top K 缓存，这就是现代搜索引擎联想功能的最小完整实现。

拼写检查是另一个经典场景。用户敲出 helo，检查器想知道词典里有没有近似词。常见做法是以 helo 为起点做编辑距离搜索：生成一次替换、删除、插入后的所有变形，比如 hello、help、hero，再到 Trie 里查这些变形是不是词。Trie 的价值在于剪枝：在生成变形的过程中，如果某个前缀在 Trie 里根本不存在，这整棵变形分支都可以放弃，不必生成完整的编辑距离矩阵。十万词的词典，编辑距离检查能压到毫秒级。

敏感词过滤则用到了 Trie 的进阶形态——AC 自动机（Aho–Corasick）：把全部敏感词插进 Trie，再给每个节点加一条 fail 指针，指向”当前已匹配后缀的最长前缀”。扫描文本时，每个字符只走一次，就能同时匹配出所有敏感词，复杂度 O(文本长度 + 命中数)。没有 Trie 做骨架，AC 自动机无从谈起；它也是第 9 节”字符串匹配系列”的核心成员之一。

8.10 应用五：词典与生物信息

别忘了一开始的需求本身：词典。英文字典、词频表、代码符号表、中文分词词表，本质都是”字符串集合 + 前缀/词频查询”，Trie 是它们最顺手的容器。在生物信息学里，DNA 序列由 A、T、C、G 四种碱基组成，正好是一个字符集大小为 4 的 Trie；基因比对、序列去重、公共片段查找都会用到基于 Trie 的索引结构，压缩后更是如鱼得水。可以说，只要世界上还有字符串，Trie 就有饭吃。

9 与字符串匹配系列的关系

熟悉本系列实验室的朋友可能已经注意到，第 3 批实验室里有一个串匹配实验室（string-viz），里面把 KMP、AC 自动机、Boyer-Moore 等算法做成了可视化交互。Trie 与它们的关系可以用一句话概括：Trie 是字符串匹配世界的通用地基。KMP 解决”一个模式串在一个文本里找位置”，它不需要 Trie；但 AC 自动机解决”几千个敏感词同时在一篇文章里找”，它就是在 Trie 上加了 fail 指针，让每次字符比较都能”自动跳回”最合适的路径。后缀树是后缀 Trie 的压缩版，后缀数组又是后缀树的紧凑实现，三者一条线传承下来。理解了今天的前缀树，再去看 AC 自动机和后缀树，会发现全是老朋友：节点、边、共享前缀、终止标记，只是换了用途。

想亲手验证 Trie 的直觉，把几个词插进去、走一走前缀，欢迎打开 串匹配实验室 玩玩看——在那里你能看到模式串在文本里怎么跳、前缀匹配怎么走，和本篇的 Trie 图对照着看，印象会深很多。

10 完整实现：组装一个自动补全类

10.1 把前面所有零件拧在一起

前面几节我们分别实现了插入、查找、删除和计数，现在把它们组装成一个真正能用的 AutoCompleteTrie：支持插入、判词、前缀判断、频率查询、删除，以及最核心的”给定前缀返回 Top K 热门候选”。

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  endCount = 0;   // 完整词出现次数
  passCount = 0;  // 经过次数
}

class AutoCompleteTrie {
  private root = new TrieNode();

  insert(word: string): void {
    let cur = this.root;
    cur.passCount++;
    for (const ch of word) {
      if (!cur.children.has(ch)) {
        cur.children.set(ch, new TrieNode());
      }
      cur = cur.children.get(ch)!;
      cur.passCount++;
    }
    cur.endCount++;
  }

  search(word: string): boolean {
    const node = this.findNode(word);
    return node !== null && node.endCount > 0;
  }

  startsWith(prefix: string): boolean {
    return this.findNode(prefix) !== null;
  }

  frequency(word: string): number {
    const node = this.findNode(word);
    return node === null ? 0 : node.endCount;
  }

  suggestions(prefix: string, k: number): string[] {
    const node = this.findNode(prefix);
    if (node === null) return [];

    const hits: { word: string; freq: number }[] = [];
    this.collect(node, prefix, hits);
    hits.sort((a, b) => b.freq - a.freq);
    return hits.slice(0, k).map((h) => h.word);
  }

  private findNode(s: string): TrieNode | null {
    let cur = this.root;
    for (const ch of s) {
      const next = cur.children.get(ch);
      if (!next) return null;
      cur = next;
    }
    return cur;
  }

  private collect(node: TrieNode, path: string, out: { word: string; freq: number }[]) {
    if (node.endCount > 0) {
      out.push({ word: path, freq: node.endCount });
    }
    for (const [ch, child] of node.children) {
      this.collect(child, path + ch, out);
    }
  }
}

这个类加起来不到五十行，却覆盖了本篇讲过的全部核心操作：insert 维护双计数，search 用 endCount > 0 取代布尔标记，startsWith 只管路径，suggestions 走”找前缀节点 → 收集子树 → 按频次排序 → 截取前 K 个”四步流程。

10.2 走查一次 suggestions

假设词典里插入过 code 两次、codex 一次、coding 三次。用户输入前缀 cod，调用 suggestions("cod", 3)。

第一步，findNode("cod") 沿着 c、o、d 走到 cod 节点。第二步，collect 从 cod 节点出发深度优先遍历，收集到三个候选：code（频次 2）、codex（频次 1）、coding（频次 3）。第三步，按频次从大到小排序，得到 coding、code、codex。第四步，截取前 3 个——候选恰好三个，全部返回。

如果用户输入的前缀在 Trie 里不存在，比如 xyz，findNode 在走到一半时就返回 null，suggestions 直接返回空数组，一个多余的遍历都不会做。如果前缀是空串，findNode 返回根，suggestions("", 10) 会返回整棵词典里最热的十个词——这正是搜索框”还没输入就展示热搜榜”的实现方式。如果 k 大于候选总数，slice 会安全地返回全部候选。

10.3 这个实现有哪些可以继续优化的地方

第一，收集阶段的遍历成本。每次 suggestions 都要把前缀下的整棵子树走一遍。如果前缀很短、子树很大，比如输入单个字母 c 而 c 下面挂着五十万词，每次联想都要遍历五十万个节点，延迟不可接受。工程优化方向是第 6 节提过的：在每个节点缓存”本子树最热 Top K”，插入时增量维护，查询时直接读缓存，复杂度从”子树大小”降到 O(K)。

第二，排序的稳定性与 Tie-break。频次相同的候选按什么顺序返回？常见做法是再加一个”字典序”或”最后访问时间”作为次级排序键，让结果稳定可预期。上面代码里 sort 是稳定的（现代 JavaScript 引擎对长度大于 10 的数组保证稳定排序），但次级键仍然值得显式设计。

第三，离线构建与只读优化。如果词典是固定的，比如输入法词库，可以先离线建好 Trie，再序列化成紧凑的二进制格式（双数组 Trie 就是这种思路），运行时只读加载，既快又省内存。前面说的”惰性删除”在这种只读场景下尤其合适：反正不回收节点，删除只把 endCount 置零即可。

10.4 用 Trie 实现词典的其他姿势

自动补全之外，同一个类稍作改造还能回答很多问题：判断一个字符串是否由词典中的词拼接而成（词法分析）；统计一段文本里每个词典词出现多少次（把文本按字符走 Trie，边走边累计 endCount）；找出所有”以某词为前缀”的完整词（startsWith 加 collect）。这些场景共享同一套骨架，变的只是遍历时对节点的处理方式。学会 Trie，等于同时学会了一整类”字符串集合索引”问题的通用解法。

11 工程细节与常见陷阱

11.1 字符集与归一化

第 3 节说过，孩子表用 Map 还是数组取决于字符集大小。工程上还有一个容易被忽视的问题：同一个字符串可能有两种写法。比如带重音的法语 é 可以存成单个字符 U+00E9，也可以存成 e 加上组合重音符号两个字符；中文虽然少见这种情况，但全角与半角、大小写、首尾空格都是同一种病。如果词典构建时用”规范化后”的字符串插入，而查询时用”未规范化”的字符串，Trie 会认为它们是不同的词。

解决办法是在所有入口做统一归一化：插入、查找、删除、联想，全部先经过同一个 normalize(word) 函数。Unicode 场景推荐 NFC 规范化（把 e + 重音合并成单字符），大小写场景统一 toLowerCase()，空白场景统一 trim。把归一化收进一个入口，比在每个方法里各写一遍可靠得多。

11.2 内存的真实账本

理论分析说”节点数 ≤ 总字符数 + 1”，但工程上每个节点都是真实对象：一个空 Map 在 JavaScript 里就要占几十字节，加上对象头、字段、GC 元数据，一百万节点的 Trie 轻轻松松吃掉上百兆内存。用定长数组存孩子时，26 个引用每个 8 字节，每节点 208 字节起步，还不算数组对象本身。

所以”Trie 空间省”和”Trie 空间费”两种说法都对，取决于参照物：和”每个词单独存完整字符串”比，共享前缀确实省；和”哈希表只存键 + 桶数组”比，每个节点的对象开销可能更贵。工程上的常见妥协是：词典小（十万以内）随便用普通 Trie；词典大且静态，用双数组 Trie 或压缩 Trie；再大，考虑分片、布隆过滤器前置过滤等更复杂的方案。

11.3 遍历顺序与字典序

第 7 节说 Trie 天然支持字典序遍历，但有一个实现细节：用 Map 存孩子时，遍历顺序是插入顺序，不是字符序。如果你先插入 zebra 再插入 apple，深度优先遍历会先输出 zebra 再输出 apple，和字典序相反。想要真正的字典序输出，要么用数组存孩子（下标天然有序），要么在遍历前把孩子按键排序。LeetCode 等平台上的 Trie 题通常默认字典序，面试时不妨主动提一句”Map 的遍历顺序由插入顺序决定，需要显式排序”——这是区分”背过模板”和”真懂实现”的小细节。

11.4 并发与持久化

Trie 是典型的”读多写少”结构：词典构建一次，查询千万次。单线程下这没问题；多线程下，多个线程同时 insert 会破坏 Map 的一致性，需要加锁或者用”构建期单线程、发布后只读共享”的策略。很多生产系统干脆离线构建 Trie、序列化发布，运行时所有请求只读——既绕开并发写问题，又获得双数组 Trie 那样的性能。

持久化也有讲究：直接把内存里的 Trie 对象序列化成 JSON，节点间的引用会变成嵌套对象，体积大且加载慢；更常见的是设计紧凑的二进制格式：节点编号 + 字符 + 孩子区间 + 计数，加载时一次读入连续内存。这又回到了”静态词典”的设计思路：Trie 的形态在查询期越”死”越好，越死越能优化。

11.5 面试与竞赛里的高频变体

竞赛和面试题里，Trie 常以这些形态出现：带计数的 Trie（词频、前缀计数）；删词 Trie（注意共享前缀）；求两个字符串的最长公共前缀（把两个词先后插入，第一个分叉点之前就是 LCP）；判断字符串集合里是否有一个词是另一个词的前缀（插入时若经过已有终点或插入后终点已有孩子，都说明存在前缀关系）；异或最大值（把数字按二进制位插进 Trie，字符集只有 0 和 1，贪心走相反位）。最后这个”二进制 Trie”是位运算题里的明星，本质和字符 Trie 一模一样，只是字符集换成了 {0, 1}。掌握了本篇的骨架，这些变体都是换汤不换药。

12 总结：一棵树，一整片字符串应用

让我们把本篇的路线图再走一遍。我们从”搜索框联想、输入法候选、IDE 补全”三个真实问题出发，发现它们共享同一个核心需求：前缀查询。哈希表在精确查找上无懈可击，却在”以什么开头”面前束手无策；于是我们引入 Trie：根为空串，边是字符，节点是前缀，终止标记区分”词”和”走廊”。插入是逐字符走、缺则建、终标记；查找分完整词与前缀两种语义；删除遵守”只拆独享尾巴”的原则；加上 endCount 和 passCount 两个计数，Trie 就能回答”谁最热”。复杂度上，所有操作都是 O(L)，与词典规模无关，这是它最迷人的性质。变体方面，压缩 Trie 合并单子长链，双数组 Trie 把树压进数组，后缀树把 Trie 推广到单个字符串，AC 自动机在 Trie 上装了 fail 指针。最后我们把所有零件组装成一个五十行的自动补全类，聊了归一化、内存账本、遍历顺序、并发持久化这些工程细节。

如果只能记住三件事，我希望是这三件：前缀查询是 Trie 的主场，哈希表替代不了；终止标记决定”词”与”前缀”的分界，一切操作都围绕它展开；操作复杂度由字符串长度决定，与词典大小无关。下一站，并查集——另一棵形态奇特、却同样无处不在的树。

13 横向对比：Trie 的对手与队友

13.1 排序数组加二分：静态词典里的实用派

很多人不知道，静态字符串词典还有一个朴素但非常能打的方案：排序数组加二分查找。把所有词按字典序排好放进数组，精确查找用二分，复杂度 O(L × log N)；前缀查询用两个二分找出”以该前缀开头的区间”：第一个二分找字典序大于等于前缀的最小下标，第二个二分找字典序严格大于”前缀的字典序后继”的最小下标，两个下标之间的整段数组就是所有候选。这个方案内存极其紧凑（一个连续数组），缓存友好，实现简单，在词典几乎不变的小型系统里甚至比 Trie 更快。

那还要 Trie 干什么？两个理由。第一，动态性：排序数组插入一个词要 O(N) 地搬动元素，Trie 插入只要 O(L)；词典频繁增删时，数组方案立刻失灵。第二，聚合能力：Trie 的节点天然携带前缀信息，词频、共享前缀、最长公共前缀都是”顺路”就能算出来的；排序数组里这些信息全部丢失，每次都要重新扫描。所以工程上的正确姿势是分场景：静态小词典用排序数组，动态或需要前缀聚合的词典用 Trie。

13.2 二叉搜索树与跳表：有序但不会”按字符走”

把字符串塞进二叉搜索树（BST）或跳表，也能得到有序集合：比较两个词按字典序，插入删除 O(L × log N)，范围查询、前驱后继都支持。它们和 Trie 的差别在于比较的粒度：BST 每次比较都要从第一个字符开始逐位比对，一趟查找要做 log N 次完整的字符串比较；Trie 则把比较打散到树的每一层，每个字符只比一次。对于”前缀查询”这个特定需求，BST 需要把前缀翻译成 [prefix, next) 的区间再过滤，Trie 则是走到节点往下看，语义直接、常数更小。

跳表比 BST 多一个优势：并发友好，可以无锁读写；很多分布式系统的有序索引用它。但跳表和 BST 都不具备”共享前缀”的存储结构，也无法回答”以 pre 开头的词一共有多少个”这类聚合问题——这类问题的答案在 Trie 里就是节点的 passCount，一行代码。

13.3 布隆过滤器：Trie 的哨兵

布隆过滤器是一种概率数据结构：它用几个哈希函数把键映射进位数组，回答”某个词肯定不在还是可能在”。它的内存小得惊人，但有两个致命限制：不能精确返回”在”（有误报），也不能枚举候选词。所以布隆过滤器通常站在 Trie 前面当哨兵：大流量场景先问布隆过滤器，回答”肯定不在”就直接拒绝，省掉 Trie 的完整查询；回答”可能在”再进 Trie 精确确认。两者是队友不是对手——一个负责廉价地排除，一个负责精确地检索。

13.4 倒排索引：不同维度的索引

搜索引擎里有两个容易混淆的部件。一个是联想（suggest）：用户输入 “tri”，下拉框给出 “trie、tree、trip”，这是词与词之间的关系，用 Trie。另一个是检索（search）：用户点击 “trie” 之后，系统要找出包含这个词的所有网页，这是词与文档之间的关系，用倒排索引——一个”词 → 文档列表”的映射，通常由哈希表或 B+ 树实现。联想面向”词库”，检索面向”文档库”，两者服务不同的查询，常常同时出现在同一个搜索框后端。理解这层分工，就不会再问”Trie 是不是能取代搜索引擎”这种问题了。

13.5 一个值得深挖的细节：按字符还是按字节

前面所有讨论都假设”一个字符 = 一层”。对纯英文这是对的；对中文，如果按 Unicode 码点分层，一个汉字占一层，字符集巨大，Map 孩子表成为必然；如果按 UTF-8 字节分层，一个汉字变成 3 到 4 个字节，树的层数变多，但每层只有 256 个可能的分支，可以用紧凑数组。按字节构建的 Trie 和按字符构建的 Trie 语义完全一样，性能特征却不同——字节版层数多、每层分支少、数组可预分配；字符版层数少、每层分支多、必须用哈希表。某些追求极致性能的词典实现会选择”UTF-8 字节 Trie”，配合压缩技术，在内存和速度上都能取得更好的平衡。

13.6 学习路径：Trie 之后看什么

如果本篇让你对字符串索引产生了兴趣，接下来的推荐顺序是：先玩转 串匹配实验室 里的 KMP 和 AC 自动机——AC 自动机就是”Trie + fail 指针”，你已经有八成基础；然后学习后缀数组与后缀树，理解”单个字符串的所有后缀”如何被索引；最后回到工程，看看双数组 Trie 在分词器、输入法里如何落地。每一步都会反复用到今天的概念：共享前缀、终止标记、路径即字符串。把这些概念焊进直觉，字符串算法的大门就彻底敞开了。

14 中文场景走查：从拼音到分词

14.1 一个中文词库 Trie

前面所有例子都是英文，Trie 的威力在中文里同样成立，只是孩子表必须用 Map。假设我们要给一个搜索引擎建词库，收录五个词：数据、数据结构、数据库、树、树林。按字符一层层插进去，得到下面的树：数据 是 数据结构 和 数据库 的公共前缀；树 是 树林 的前缀；数据 和 树 虽然都含”数”字，但 数据 的第一个字符是”数”、树 的第一个字符也是”树”——等等，这里要小心：“数据”的”数”和”树”是不同字符，它们在第一层就分开了。

这棵树和英文 Trie 没有任何结构差异：根到节点的路径是中文串，数据 节点带终止标记同时又有两个孩子，树 节点同理。插入中文词时，for 循环遍历的是字符串的每个字符，JavaScript 的 for...of 天然按码点遍历，汉字一次一个，不会把汉字拆成两个代理项；但要注意，如果按 charCodeAt 或者某些旧式下标访问，就可能在生僻字（如 emoji 或补充平面的汉字）上出错。用 for...of 或 Array.from 处理，中文 Trie 的实现和英文完全一样。

14.2 输入法联想的走查

用户在搜索框输入”数”，suggestions("数", 10) 走到”数”节点，然后 collect 遍历子树，收集到 数据、数据结构、数据库 三个候选。如果 数据 被搜索了 1000 次、数据库 800 次、数据结构 200 次，排序后联想顺序就是数据、数据库、数据结构——完全符合用户预期。这里有个细节：数据结构 以 数据 开头，所以它也会出现在”数”的候选里；而 树、树林 因为第一个字符不同，永远不会出现在”数”的候选里。这正是 Trie”按字符分组”的语义，也是它和”包含匹配”（子串匹配）的区别：前缀树只认前缀，不认包含。想找”包含数据”的词，需要后缀树或全文索引，而不是前缀树。

14.3 中文分词的”最大正向匹配”

中文没有天然空格，分词是很多系统的第一步。一个朴素但广泛使用的方法是最大正向匹配（Maximum Matching）：从句子开头取指针，在词库 Trie 里尽量往前走，走到不能再走时，把最后经过的带终止标记的位置截出来作为一个词，然后从那里继续。

举个例子，句子”数据结构很实用”，词库就是上面那棵 Trie。指针从”数”开始，沿 Trie 走到”数”→“据”→“结”→“构”，路径上的词有 数据 和 数据结构，再往下”很”没有孩子，于是按”最长匹配”原则切出 数据结构；指针移到”很”，Trie 里没有”很”开头的词，按单字处理；“实”、“用”同理。整个过程每个字符只走一次 Trie，复杂度 O(句子长度 × 最大词长)。这棵”词库 Trie”就是分词器的最小核心，进阶版会在每个节点上挂词频、在树上做动态规划寻找全局最优切分——但骨架仍然是今天学的这棵树。

14.4 敏感词与拼音的延伸

中文敏感词过滤同样是 AC 自动机的典型战场：把几千个敏感词插进 Trie，构建 fail 指针，扫描一篇文章时每个字符只处理一次，命中即报警。拼音输入法更复杂一些：候选不仅是词，还有”拼音串 → 候选词序列”的映射，以及语言模型打分；但”拼音前缀 → 候选集合”的索引依然是一棵（或几棵）Trie。可以说，从搜索联想、分词、敏感词到输入法，中文互联网的每一个”打字相关”功能背后，都站着一棵前缀树。

14.5 编辑器、数据库与更多隐藏身影

现代代码编辑器把符号表组织成 Trie 已经见怪不怪，但你可能没注意过数据库：许多数据库的索引前缀压缩（比如 B 树变体里的 key prefix truncation）和 Trie 的”共享前缀”思想同源；Redis 的字典、磁盘上的 LSM 键排序，也都绕不开”前缀有序”这个 Trie 最擅长的性质。甚至操作系统的文件系统路径解析、URL 路由匹配、CDN 的边缘节点调度，都在用压缩 Trie 或类似结构做最长前缀匹配。下次你敲下一个字符就弹出补全、输入网址就命中缓存时，可以想一想：这背后很可能就是一棵把共享前缀存了无数遍、却让每次查询只走 L 步的树。

回到我们最初的问题：词典、输入法、搜索框的”前缀补全”怎么做？答案已经完整铺开——把字符串按字符拆成树，让共享前缀合并成同一条路径，让每个字符只被比较一次。这个答案朴素、稳定、可扩展，从几十个词的玩具词典到上亿条目的工业词库，思想始终如一。数据结构之美往往就在这种地方：不是技巧有多精巧，而是当问题被问对之后，答案天然地长成一棵树。

哪怕你今天只记住了”边走边建、终点标记”八个字，也已经握住了 Trie 的钥匙：剩下的查找、删除、统计，都不过是沿着这把钥匙自然展开的推论。

写在最后

至此，树系列从”为什么需要树”走到了”字符串的树”。Trie 是少有的”定义三句话、操作四行代码、应用一整片天”的结构：它不追求花哨，只做一件事——把前缀组织成路径，然后让查询顺着路径走。下一篇《树系列第 18 篇：并查集》，我们将看到树的方向被反转、边的含义变成”归属”，那又会是一番完全不同的风景。在此之前，不妨打开 串匹配实验室，亲手插几个词、查几个前缀，让这棵前缀树在你手里真正”活”一次。

速查表

操作	时间复杂度	核心要点
插入	O(L)	逐字符走，没有孩子就新建，最后打终止标记
完整词查找	O(L)	路径存在，且终点 isEnd 为 true
前缀查找	O(L)	只要求路径存在，不要求终点是词
删除	O(L)	只删”独享尾巴”：既不是词终点、又没有孩子的节点
词频统计	插入时 O(L) 更新	endCount 记完整词次数，passCount 记经过次数
自动补全	O(L + 子树节点数)	前缀节点 + 子树收集 + 按频次排序取 Top K
空间	O(S × 字符集) 或 O(S)	节点数 ≤ 总字符数 + 1；孩子表用数组还是 Map 决定常数

三句话总结：Trie 把字符串按字符拆成树，共享前缀只存一遍；一切操作的时间只和字符串长度有关，和词典大小无关；终止标记是”词”与”前缀”的唯一分界线。

自测题

下一篇预告

《树系列第 18 篇：并查集》来了。如果 Trie 是把字符串组织成树，那么并查集就是把集合之间的关系组织成树：每个人只有一个”父亲”，顺着父亲一直往上能找到自己所在集合的”掌门”；合并两个集合，就是把一棵树的根接到另一棵树的根上。并查集的树长得很特别——孩子指父亲，方向和我们习惯的树相反；再配上路径压缩和按秩合并，四行代码就能做到几乎常数时间的”查询是否同伙、合并两支队伍”。下一篇我们会从连通性问题、朋友圈、动态连通性的故事讲起，看看这棵”倒着长”的树为什么能成为算法竞赛和工程里最实用的数据结构之一。到时候见！