什么是压缩字典树（Radix Tree / Patricia Trie）？

简化版

普通 Trie 里，很多节点只有一个孩子，形成一长串「单链」，浪费节点。压缩字典树（Radix Tree / Patricia Trie） 把这些「只有一个孩子的连续节点」压成一条边，边上存一个字符串（而不是单个字符）。这样节点数大幅减少、更省空间、查询更快。典型用于 IP 路由表的最长前缀匹配、Redis 的 stream/字典、文件系统索引。

详细版

普通 Trie 存 {"team", "test"}：

普通 Trie（t-e 之后才分叉，中间节点都是单链）:
t → e → a → m
        └ s → t

压缩后（把单链 "te" 压成一条边，分叉后也压缩）:
      "te"
      /   \
   "am"   "st"

核心变化：边不再是单个字符，而是一段字符串；只在「真正分叉」的地方才设节点。
效果：节点数从「字符总数」降到「大约等于单词数 + 分叉数」，空间显著减少，路径更短、查询更快。

Radix Tree 和 Patricia Trie 常被当作同义词，都指这种「路径压缩的 Trie」（Patricia 最初特指基数为 2 的二进制版本，现在泛化了）。

完整版教学

一、普通 Trie 的浪费：单链节点

普通 Trie 里，如果一段前缀只被一个单词使用（没有分叉），就会形成一串「每个节点只有一个孩子」的链。比如只有 internationalization 一个词，就会有 20 个各自只有一个孩子的节点，除了浪费还拉长了查询路径。这些「单孩子链」不承载任何「分支决策」信息，纯属冗余。

二、路径压缩：把单链合并成一条边

压缩字典树的思想是：只在”需要做分支选择”的地方保留节点，把中间的单孩子链压缩成一条边，边上存整段字符串。于是：

一个节点要么是叶子，要么至少有两个孩子（是真正的分叉点）。
边从「代表一个字符」变成「代表一个字符串（子串）」。

这样节点数从 O(字符总数) 降到 O(单词数)，空间和查询路径都大幅优化。

三、查询怎么变

查询时不再逐字符走，而是逐边比较字符串：

在当前节点，找到「首字符匹配」的那条边。
拿目标串的对应部分和边上的字符串逐字符比对。
完全匹配就走到边的另一端继续；部分匹配或不匹配则查询失败（或在此分裂，若是插入）。

插入时如果新词和某条边只匹配了一部分，就要分裂这条边：在匹配结束处插入一个新的分叉节点。

四、典型应用

压缩字典树在工程里非常常见，尤其是最长前缀匹配和内存敏感的场景：

IP 路由表：路由查找是「找最长匹配的网段前缀」，用 Radix Tree（如 Linux 内核的 LPC-trie）高效实现最长前缀匹配。
Redis：Stream 类型的底层、以及早期的字典实现用到了 radix tree（rax） 来省内存。
文件系统 / 数据库索引：如 Linux 内核用 radix tree 管理页缓存（按页号索引）。
IP 地理位置库、前缀路由等。

五、和普通 Trie / 哈希的取舍

普通 Trie：实现简单，但单链浪费严重、空间大。
压缩 Trie：省空间、路径短、查询快，但实现复杂（要处理边的分裂/合并）。
哈希表：等值查找快，但不支持前缀 / 最长前缀匹配。

需要前缀操作 + 省空间时，压缩 Trie 是普通 Trie 的更优替代；只做等值查找用哈希。

六、常见误区与追问

考点	正确口径
普通 Trie	每条边一个字符，单链节点可能很多
压缩 Trie	把连续单分支压成字符串边
收益	减少节点数，提高空间利用率

ordinary: c -> o -> d -> e
compressed: "code"

压缩 Trie 压缩的是路径，不是丢掉字符；匹配时要按边上的字符串逐段比较。

误区：压缩后就不能做前缀查询。 仍然可以做前缀查询，只是匹配单位从单字符变成边标签字符串。
误区：压缩 Trie 查询一定更快。 节点数减少，但每条边可能要比较多个字符，复杂度仍与字符串长度相关。
误区：Patricia Trie 只用于字符串。 Patricia 常用于二进制位串、路由前缀等场景，本质是压缩路径。
追问：插入时遇到部分匹配怎么办？ 需要把边拆分成公共前缀、旧后缀和新后缀三段，再挂对应子节点。
追问：和普通 Trie 的取舍是什么？ 普通 Trie 简单，压缩 Trie 省空间但实现复杂。
追问：典型应用有哪些？ IP 路由表、字典存储、搜索前缀索引等都可能用到路径压缩思想。

七、加强记忆

压缩字典树（Radix Tree / Patricia Trie）把普通 Trie 里「只有一个孩子的连续节点」压成一条边、边上存字符串，只在真正分叉处保留节点。节点数从 O(字符总数) 降到 O(单词数)，省空间、路径短、查询快；查询逐边比较字符串，插入时可能分裂边。典型用于 IP 路由最长前缀匹配、Redis rax、内核页缓存。要前缀操作又省空间就用它。

简化版

详细版