跳转至

第 16 章 数字查找树 — 按字符走,不按比较走

这一章讲什么: 当键是字符串,查找可以不用「比较大小」, 而是「一个字符一个字符地走」——trie(字典树)一族。 查找时间与键长成正比、与词库大小无关,还天然支持前缀查询(自动补全)。 它在全书链条里的位置:第 12 章 BST 的「键不可分解」假设在这里被打破; 第 6 章基数排序「不比按键分解」的思想在查找侧的对应物。

1. 顶层全景

  经典 trie:
    节点 = 字符槽位数组(A–E + ■);键 = 从根出发的路径;词尾用 EOW(■)挂数据
    查找 BED:走 B → E → D → ■,每步一个槽位;O(k),k = 键长
    前缀即子树:自动补全 = 走到前缀然后遍历子树
      │
      ├─ 问题:单链浪费层数(没人分岔的字符各占一层)
      │
      ├─ 基数树(radix tree):把单孩子的链接并入父链接 → 多字符边
      │    查找 = 逐层做「公共前缀匹配」(_commonLength)
      │    BADE 两层就到;插入可能要「劈开」一条边(一分为二)
      │    删除则可能「上推合并」一条边(撤销劈开)
      │
      └─ 三元查找树(TST):节点只存一个字符 + 左/中/右三根链接
           字符 < 节点键 → 左;相等 → 中(消耗一个字符);> → 右
           = BST 查找逻辑 + 「相等往中走、消耗字符」
           删除 = 路径裁剪 + BST 式顶替(按孩子数分三支)
           空间远小于 trie(每节点 3 指针 vs 整字符表)

  图说:同一组词(ACE, AD, BADE, BE, BED, BEE)的三种住法:
  trie 用层数换简单,radix 用劈边换矮,TST 用三个指针换省。

2. 主线例子:词库 {ACE, AD, BADE, BE, BED, BEE} 的三种查找走查

经典 trie 查 BED:根上 B 槽非空 → 下一层 E 槽非空 → 再下一层 D 槽非空 → ■ 槽挂着数据 → 命中返回 data。失败例 1:DAB——根的 D 槽就是空,第一步就败; 失败例 2:ACED——A、C、E 都通,但下一层没有 D 槽,败; 失败例 3(最微妙):BAD——B、A、D 都通,但 ■ 槽是空的: BAD 是某个词(BADE)的前缀,却不是词本身——EOW 槽就是区分 「前缀」与「词」的那一位2。

基数树查 BED■:根上找「首字符是 B 的边」→ 剩 ED■;下一层找首字符 E 的边 → 剩 D■;再下一层找到 D■ 完整匹配 → 命中。两层半就到,而 trie 要走四层。 查 ACED■:A 边通,剩 CED■,下一层没有以 C 开头的边 → 败7。

TST 查 AD■:根是 B,AC 走右;遇到 D,相等走中,剩 ■;再中是 ■ → 命中返回 data。 查找逻辑与 BST 几乎逐行相同,只是「相等」分支往中走并吃掉一个字符9。

3. 核心原理

3.1 trie:键分布式存储,所以一切按路径算

Trie 里没有一个节点存着完整的键——键被拆散在路径上 (ACE 的 A 在第一层节点、C 在第二层、E 在第三层)。 三个直接后果(书中明说):EOW 字符必不可少(否则无法区分 「词」与「词的前缀」);查找/插入/删除全是 O(k)、k = 键长 ——与词库里有多少词无关(BST 是 O(log n));附带数据要挂在 EOW 节点的链接上而不是键节点上1。 节点用「每字符一槽」的数组实现最直白;「增强版」改用对象做稀疏链接 (省内存),删除需要递归回收空节点4。

3.2 基数树:压缩单链

经典 trie 的层数 = 最长键长,哪怕一大段路没人分岔。 基数树的规则:任何只有一个孩子的内部链,并入父链接, 于是边可以带多个字符(如直接一条 "BADE" 边)。 实现要点在「劈边」:插入时若新键与某条边只有部分公共前缀, 就把那条边劈成两段、中间新插一个节点;查找用公共前缀函数 _commonLength 逐层消耗字符串6。

3.3 基数树的删除:上推合并,撤销劈边

解决什么问题. 劈边保证了「树里不存在只剩一条出边的内部节点」; 删除若只是把词的最后一摘,可能留下单链节点——压缩不变式被破坏, 它不再是基数树,查找还多白走一层。原书把删除的结局分成两种,由简到繁讲10。

怎么做. 先照 3.2 的查找法搜到这个词(同样补上词尾 ■),然后分两种结局:

  • 删后还剩两条以上链接——直接摘。 删 ACE:根上走 A 边,剩 CE■; 下一层找到与剩余部分完全相等的整条链接 CE■,删掉即完事。 所在节点本来还有 D■、BE■ 两条链接,树的形状一点没变。
  • 删后只剩一条链接——上推合并。 删 BADE:走 B 边、再走 AD 边,删掉最后一条链接 E■; 此时 AD 节点只剩 ■ 一条链接,成了单链。按压缩规则把它上推: 与父链接 AD 合并成一条 AD■ 边,直接挂回 B 节点,中间节点消失。 这正好是插入时那次劈边的逆操作——原书称之为「撤销劈边」。

代码 _remove() 的结构与查找逐层同款:找不到首字符相同的链接 → 词不在树里,收工; 链接与待删词完全相等 → 删链接收工;否则算出公共前缀,递归删剩余部分; 递归回来后检查到达的节点——若只剩 1 条链接,把「前缀 + 单链接」拼成一条新边 挂回本层、删掉中间节点。外层的 remove() 负责补上 ■, 并在删完后检查:根节点空了,整树置 null10。

为什么有效. 上推合并不丢词:被合并节点里剩下的词都走那条单链接, 字符接回一条边之后,查找照旧「按首字符一步定位、按公共前缀逐层消耗」。 而「删后剩 ≥2 链接就不动」防止过度合并——还有分岔的节点必须留在原地。 两种结局都保住了查找赖以定位的那条不变式:同一节点的各条链接,首字符互不相同。

边界. 待删词不存在时静默收工(找不到首字符相同的链接), 与经典 trie 删除「先找,找不到就无事发生」一致; 只有「删后恰好单链」才触发合并;整个词恰好就是一条边时直接删边, 下方节点随边一起脱离,无需专门清理。

3.4 TST:空间与代码的折中

Trie 每个节点的槽位数 = 字符集大小(26 个字母就 26 槽 + EOW), 词库稀疏时浪费惊人。TST 把「字符 → 槽位」换成「字符 → 三次比较」: 每个节点只存一个字符,左中右三指针;相等时往中走并前进到下一个字符, 不等时按大小走左右(BST 本色)。空间从 O(字符集) 降到 O(3)。 至于速度,原书给的口径与另外两个结构同档:增、删、查都是 O(sk) (k = 键长,s = 字符集大小),并强调 sk 是常数、「其实就是 O(1)」。 但 TST 有一个本章其他 trie 都没有的变数:树的形状取决于插入和删除的 顺序,最坏情况与平均情况不同——和第 12 章的朴素 BST 同病12。

3.5 TST 的删除:路径裁剪 + BST 式顶替

解决什么问题. TST 里键不存放在单个节点,而是散在中链上; 删一个词要动好几个节点——删多了会弄断别的词,删少了白留废节点。 原书的讲法与第 12 章 BST 删除同源:按被删节点有几个孩子分情况,共三支11。

怎么做.

  • 路径裁剪(词独占的尾巴). 删 BEAD、BEVY 或 BELL:从 ■ 开始沿原路往回删, 一直删到「还属于别的路径」的节点为止——原书把停手处叫 cut(切口)。 切口节点自己的中链(有的还带一条侧链,如 BEST)不能动,别的词还要走。
  • 单孩子直挂. 删 BETS:删完后 T 节点只剩一个孩子,留着浪费; 像 BST 删单孩子节点一样,让父节点直接改指那个非空孩子。
  • 左右都有——取右子树最左节点顶替. 删 BED:D 节点左右链接都非空, 直接摘会弄丢许多别的词;留着又不是任何词的一部分。解法是第 12 章 BST 的后继顶替法:到右子树里找下一个词(原书例:BEER 顶替 BED)换进被删位置, 再修好周围的链接。若右孩子本身没有左孩子,链接调整更简单 (原书留了个对照练习:删 BEST,用 BEVY 顶替)。

代码 _remove() 与查找同骨架:空树 → 无事;词走完(越过 ■)→ 本节点置 null; 字符等于节点键 → 递归删中链(键是 ■ 则把中链置 null); 删完发现中链空了,才轮到按孩子数分情况——左空取右、右空取左; 左右都非空,则到右子树沿左链走到最左节点 treeR:若它上面还有左祖先(prev), 先把 prev 的左链接到 treeR 的右子树、让 treeR 的右接管整棵右子树, 再让 treeR 的左接管整棵左子树,treeR 顶到被删位置(自己的中链原样保留); 字符不等 → 按大小递归左或右。外层 remove() 仍是补 ■ 后调 _remove()11。

为什么有效. 裁剪安全,是因为被裁节点「中链已空」——它后面不再接任何词, 只属于被删词;停在切口,就保住了还属于别的词的节点。顶替安全,是因为右子树的 最左节点是「比被删键大的最小者」:左子树全比它小、右子树全比它大, BST 的顺序不被打破;它又恰好没有左孩子,从右子树里摘它只需接一次链接。 TST 的横向(左右)链接本来就是对 BST 的复用,所以删除也能整套照搬—— 这正是 3.4 节「学习成本被刻意压低」的延续。

边界. 三支与 BST 删除一一对应(0 / 1 / 2 个孩子),没有第四种形态; 待删词不存在时递归自然走到空树,无事发生; 右孩子本身就是最左节点(prev 为空)时,链接调整退化为最简单的直挂。

3.6 三者怎么选

经典 trie 基数树 TST
空间 最费(槽位数组) 省(稀疏对象) 最省(3 指针/节点)
层数/速度 键长 k ≤ 键长,常更矮 键长 + 横向导航(最坏看增删顺序)
前缀/补全 天然支持 天然支持 走中链后遍历
删除 递归回收空链 上推合并单链 裁剪路径 + 按孩子数顶替
实现复杂度 低 中(劈边) 中(复用 BST)

字符集小且键密集 → trie;键长、单链多 → radix;内存紧、键稀疏 → TST。

4. 作者的判断与证据

  • O(k) 与 n 无关是本章的卖点,性能表直接写 O(k) 三操作; 与前 15 章的 O(log n) 家族形成对照(代价:只适用于可分解的键)3。
  • EOW 的三次失败走查(不存在/前缀差一位/是前缀非词)是原书精心设计的 教学序列——把 trie 查询的全部边界一次演完2。
  • TST 的正当性来自复用:「定义与 BST 类似,加一根 middle 链接」 ——学习成本被刻意压低,删除的三个分支也整套照搬 BST8。
  • TST 的性能口径是「形状决定」:原书明说 TST 与本章其他 trie 不同—— 树形取决于增删顺序,最坏情况与平均情况不同,和第 12 章朴素 BST 一样; 给的数字仍是 O(sk)(k 键长、s 字符集),并补一句「sk 是常数, 所以其实是 O(1)」——与其他 trie 同档12。
  • 发音注(trie 读 tree 或 try 均可)、老电话索引的类比、 Scrabble 查词的例子——轻松的笔法,但不承载论断。

判断(我们的,不是书里的): trie 家族的本质是把「键空间」 从「全序集」换成「字符树」,于是查找从「与 n 赛跑」变成「与 k 赛跑」。 这个视角解释了为什么自动补全、IP 路由(最长前缀匹配)、 词频统计全都首选 trie——它们的键天然是字符串,且 k ≪ log n。 但注意边界:键不可分解(如浮点数、复合对象)时整个家族失效, 退回哈希或 BST。 如果错,会错在: 「k ≪ log n」不恒成立——长键(k 上百的 DNA 序列、 URL)时 O(k) 会吃掉优势,工程上常配合哈希前缀压缩(补充,不在书里,来自通用知识)。

5. 边界与局限

  • 字符集大了槽位数组爆炸:本章只用 A–E 演示,真实 26 字母 + 大小写 + Unicode 必须稀疏化(对象/Map)或用 TST;
  • 哈希 vs trie 的比较缺席:trie 不支持 O(1) 精确命中(最坏 O(k)), 哈希表才是纯查找的常数赢家;trie 赢在前缀操作(书中以自动补全暗示, 未展开为完整对比);
  • 删除的空节点回收经典版已处理:_remove 递归返回后用 links.every(isEmpty) 检查,全空的节点自底向上置 null 回收5;
  • TST 的形状依赖增删顺序:最坏情况与平均情况不同(与朴素 BST 同病), 原书只点到现象,未展开修复方案12;
  • 压缩的更激进形式(前缀树 PATRICIA)未提及(补充,不在书里)。

6. 可带走的

  1. Trie 三要素:字符槽位节点、EOW(■)词尾标记、数据挂 EOW。
  2. O(k) 三操作,与词库规模无关;前缀即子树 → 自动补全的基础设施。
  3. 三种失败各认脸:首字符无槽(早败)、中途断链、是前缀但无 EOW(最微妙)。
  4. 基数树:单链压缩成多边,插入会劈边;查找逐层做公共前缀匹配。
  5. 基数树删除两结局:删后剩 ≥2 链接直接摘;只剩 1 链接则上推合并进父边(撤销劈边)。
  6. TST:节点一字符三指针,等走中(耗字符)、小走左、大走右;BST 逻辑复用。
  7. TST 删除三支:从 EOW 往回裁到切口;单孩子让父节点直挂; 左右都有取右子树最左节点顶替。
  8. TST 速度口径:O(sk) ≈ O(1) 与词库规模无关, 但树形(最坏情况)取决于增删顺序。
  9. 选型:字符集小选 trie,键长单链多选 radix,内存紧选 TST。

7. 原文地图

主题 原书章 原文位置
trie 定义与电话索引类比 The Classic Version of Tries text/53-fm-the-classic-version-of-tries.txt:43(搜「telephone」) · text/53-fm-the-classic-version-of-tries.txt:46(搜「EOW」)
EOW 与分布式键 The Classic Version of Tries text/53-fm-the-classic-version-of-tries.txt:55(搜「six-ary」) · text/53-fm-the-classic-version-of-tries.txt:82(搜「distributed」)
查找三种走查 The Classic Version of Tries text/53-fm-the-classic-version-of-tries.txt:187(搜「successful」) · text/53-fm-the-classic-version-of-tries.txt:208(搜「prefix」)
性能 O(k) The Classic Version of Tries text/53-fm-the-classic-version-of-tries.txt:407(搜「O(k)」)
基数树压缩与查找 The Classic Version of Tries text/53-fm-the-classic-version-of-tries.txt:639(搜「push it up」) · text/53-fm-the-classic-version-of-tries.txt:695(搜「common」)
基数树删除(上推合并) The Classic Version of Tries text/53-fm-the-classic-version-of-tries.txt:828(搜「Removing a Key from a Radix」) · text/53-fm-the-classic-version-of-tries.txt:856(搜「push it up」)
TST 三链接 The Classic Version of Tries text/53-fm-the-classic-version-of-tries.txt:992(搜「three links」) · text/53-fm-the-classic-version-of-tries.txt:1081(搜「_find」)
TST 删除(三支) The Classic Version of Tries text/53-fm-the-classic-version-of-tries.txt:1160(搜「Removing a Key from a Ternary」) · text/53-fm-the-classic-version-of-tries.txt:1198(搜「right subtree」)
TST 性能(O(sk) 与形状依赖) The Classic Version of Tries text/53-fm-the-classic-version-of-tries.txt:1271(搜「shape of the tree depends」) · text/53-fm-the-classic-version-of-tries.txt:1274(搜「O(sk)」)

  1. 出处:「The Classic Version of Tries」第 46、55、64 段(text/53-fm-the-classic-version-of-tries.txt:46,搜「EOW」;:55,搜「six-ary」)。原文:节点为每个可能字符(A–E + ■)各设一个链接,本质是六叉树;「可以称我们为 trie 定义基本函数」。 ↩

  2. 出处:「The Classic Version of Tries」第 178–231 段(text/53-fm-the-classic-version-of-tries.txt:187,搜「successful」;:190,搜「ACED」;:208,搜「prefix」)。原文:BED 走查成功;ACED 中途断链;BAD「是至少一个词的前缀,但 EOW 链接缺失,所以不算在 trie 里」。 ↩↩

  3. 出处:「The Classic Version of Tries」第 362–447 段(text/53-fm-the-classic-version-of-tries.txt:407,搜「O(k)」)。原文:性能表 add/remove/find 均 O(k)。 ↩

  4. 出处:「The Classic Version of Tries」第 447 段(text/53-fm-the-classic-version-of-tries.txt:447,搜「Enhanced」)。原文:增强版用对象存链接以节省空间,删除时递归回收空子树。 ↩

  5. 出处:「The Classic Version of Tries」第 334–347 段(text/53-fm-the-classic-version-of-tries.txt:334,搜「_remove」;:342,搜「every」)。原文:经典数组版 _remove 递归处理剩余字符后,若 trie.links.every((t) => isEmpty(t)) 则将该节点置 null——删除路径上变空的节点在递归回溯时被逐层回收。 ↩

  6. 出处:「The Classic Version of Tries」第 631–747 段(text/53-fm-the-classic-version-of-tries.txt:639,搜「push it up」;:701,搜「_commonLength」)。原文:单链并入父链接缩短路径;查找逐层匹配前缀;「BADE 只需两步」。 ↩

  7. 出处:「The Classic Version of Tries」第 681–692 段(text/53-fm-the-classic-version-of-tries.txt:681,搜「prefix」)。原文:BED■ 逐层消耗;ACED■ 第二层找不到 C 开头边即失败。 ↩

  8. 出处:「The Classic Version of Tries」第 992–1014 段(text/53-fm-the-classic-version-of-tries.txt:992,搜「three links」)。原文:左 = 当前字符小于节点键,中 = 等于,右 = 大于;「定义与二叉搜索树类似,加一根中链接」。 ↩

  9. 出处:「The Classic Version of Tries」第 1061–1100 段(text/53-fm-the-classic-version-of-tries.txt:1081,搜「_find」)。原文:等则走中并消耗字符,不等按大小走左右;与 BST 逻辑逐行对应。 ↩

  10. 出处:「The Classic Version of Tries」第 828–903 段(text/53-fm-the-classic-version-of-tries.txt:828,搜「Removing a Key from a Radix」;:856,搜「push it up」;:878,搜「length === 1」)。原文:两种结局——删后剩 ≥2 链接(删 ACE,摘整条 CE■ 即可)与删后单链(删 BADE,删 E■ 后把仅剩的 ■ 上推、与父链接 AD 合并成 AD■);「这撤销了添加新键时的那种劈边」;代码在递归回来后检查子节点是否只剩单键,是则合并。 ↩↩

  11. 出处:「The Classic Version of Tries」第 1153–1260 段(text/53-fm-the-classic-version-of-tries.txt:1160,搜「Removing a Key from a Ternary」;:1174,搜「BEAD, BEVY, or BELL」;:1198,搜「next word in its right subtree」;:1254,搜「leftmost node at the right」)。原文:键不散存在单节点,删词要沿路径从 EOW 往回删多个节点、到汇入别路处停;单孩子按 BST 直挂;左右都有时取右子树的下一个词顶替(BEER 顶替 BED);右孩子无左孩子时调整更简单(练习:删 BEST 用 BEVY)。 ↩↩

  12. 出处:「The Classic Version of Tries」第 1268–1274 段(text/53-fm-the-classic-version-of-tries.txt:1271,搜「shape of the tree depends」;:1274,搜「O(sk)」)。原文:三元树的形状取决于增删顺序,最坏情况与平均情况不同(与朴素 BST 相同);k 长键、s 字符集,增删查均 O(sk),「严格说 sk 是常数,所以其实是 O(1)」,与其他 trie 性能相同。 ↩↩↩