二进制 Trie 与 Patricia 压缩

普通二进制 trie 把每一位都画成一层，即使一段前缀上从未出现选择也照样占节点。Patricia 压缩只删除这些“没有决定作用”的层，并在保留下来的节点记录真正发生分叉的位；查询的方向判断因此不变，但被跳过的位必须在候选叶上一次性核对。

八位例子 ​

图先展示两个键 00101100、00101101：前七位相同，只有最低位不同，压缩后只保留 $d=0$ 的分叉和两个叶。若再加入 11100000，就增加一个 $d=7$ 的根；其 0 支指向原来的 $d=0$ 子树，1 支指向新叶。

查询未存储的 00111100 时，第 7 位为 0、第 0 位也为 0，仍会走到 00101100。完整比较发现第 4 位不同，才能返回“不存在”。这是压缩省略的位必须在叶子核对的具体原因。

若允许重复键，可在叶维护出现次数；集合接口则直接报告已存在。字符串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$；若 $x=y$，按重复键规则处理并停止。否则计算 $d=\mathrm{msb}(x\oplus y)$，即二者最高不同位的编号。沿现有路径找到第一个分叉位低于 $d$ 的位置，插入记录 $d$ 的内部节点，并按 $x$ 的第 $d$ 位连接新叶，另一支接原来的子树。若途中先到叶，就在该叶之前插入。路径分叉位严格递减（从高位到低位），因此搜索不会倒退。

到叶后必须完整比较：压缩路径跳过的位可能不同。节点 $O(n)$ 只解决空间；一条路径最多有 $min(w,n-1)$ 个分叉，既受不同位数限制，也受内部节点总数限制。当 $w$ 足够大时高度可以达到 $n-1$，所以压缩并不保证 $O(\log n)$ 的平衡高度。

与字符串 Trie 的分界 ​

字符串 trie 的边按字符、深度按字符串长度；Patricia 原论文可处理字符串，但本页整数版本把键装入一个 Word-RAM 字；若允许常数时间 xor 和最高置位定位 msb，就可由两键异或常数时间找到分叉位。仅声明 Word-RAM 尚未固定 msb 的实现，应在允许指令或预处理条件中说明。若键跨多字，msb 和比较成本需重新计。