二进制 Trie 与 Patricia 压缩

结构 ​

$w$ 位整数按最高位到最低位进入二进制 trie，查找与前驱基线为 $O(w)$，空间可达 $O(nw)$。Patricia 压缩无分叉路径，内部节点只保存分叉位，叶保存完整键，节点数 $O(n)$。

搜索按分叉位下降到候选叶后仍须与原键完整比较；压缩边没逐位验证，不能因到叶就断言命中。路径上分叉位必须严格递增。

八位例子 ​

键 00101100、00101101、11100000 在普通 trie 有长共同路径。Patricia 只保留最高位分叉和左侧最低位分叉，加三个叶。压缩降低节点数，却不保证树高 $O(\log n)$；最坏仍可有 $n$ 个分叉。

重复键应在叶维护 multiplicity。字符串Trie公理库字典树Trie · Prefix tree按字符串前缀共享路径组织键集合的树形数据结构。允许变长字母边，整数版本依赖固定字长和位操作，二者不能只因名称相同而混写复杂度。

叶节点若只保存指向外部键的引用，查询到叶后仍须读取完整键核对。否则压缩路径跳过的位无法验证，membership 可能把邻近但不同的键误报为命中。

普通二进制 Trie 的前驱过程 ​

查询位串从根逐位走；若下一位分支存在就继续。若查询位为 1 而 1 支不存在，转入 0 支后取其中最右叶；若查询位为 0 而 0 支不存在，必须向祖先回退，找到最近一次可以从 1 支改走 0 支的位置，再取最右叶。保存子树 min/max 或叶双链可把恢复路径说清。

对键 00101100、00101101、11100000 查询 00101110，左子树定位后候选 00101101；查询 00000000 则无前驱。每步最多处理一个位，时间 $O(w)$，与压缩节点数无关。

Patricia 插入不变量 ​

搜索新键 $x$ 到候选叶 $y$，计算 $d=msb(x\oplus y)$。沿现有路径找到第一个分叉位低于 $d$ 的位置，插入记录 $d$ 的内部节点，并按 $x$ 的第 $d$ 位连接新叶。路径分叉位严格递减（从高位到低位），因此搜索不会倒退。

到叶后必须完整比较：压缩路径跳过的位可能不同。节点 $O(n)$ 只解决空间；分叉高度最坏仍 $n$，所以 Patricia 不是平衡树。

与字符串 Trie 的分界 ​

字符串 trie 的边按字符、深度按字符串长度；Patricia 原论文可处理字符串，但本页整数版本把键装入一个 Word-RAM 字并用 xor/msb 常数定位分叉。若键跨多字，msb 和比较成本需重新计。

参考资料

• Donald Morrison, “PATRICIA,” JACM, 1968.
• Donald Knuth, TAOCP, Vol. 3, 1998.