咨询：Patricia Trie（r=2基数树）与二进制前缀树的差异及猜测验证

先明确二者的本质区别：Patricia Trie的核心是对无分支路径的压缩优化，而二进制前缀树是无压缩的逐比特节点结构，以下针对你的猜测展开说明：

对两个猜测的反馈 #

1. 你的第一个猜测方向正确，但需要补充完整：
   • Patricia Trie的边确实会存储连续比特序列（而非单个比特），但这种压缩不仅限于父节点到叶子的单链，所有无分支的连续路径都会被合并。比如多个字符串共享一段连续无分歧的前缀时，这段前缀不会被拆分成单个比特节点，而是直接作为一条边的存储内容，仅在出现分支的比特位创建节点。
   • 边的结构通常包含：连续比特的长度/具体值、子节点指针；终止节点只需标记该位置对应完整字符串（无需额外存储完整单词，除非是为了快速返回结果）。
2. 你的第二个猜测错误：二者的核心差异正是路径压缩，这也是Patricia Trie空间优化的关键。二进制前缀树会为每个比特位创建独立节点，哪怕路径上没有任何分支，导致大量冗余节点；而Patricia Trie通过合并无分支路径，大幅减少了节点数量，这才是空间优势的来源。

核心差异总结 #

• 二进制前缀树：
  • 每个节点对应单个比特位，每个节点包含0、1两个子节点指针
  • 无论路径是否有分支，都会逐比特生成节点，空间冗余度高
  • 查询时需要逐个比特遍历节点，效率较低
• Patricia Trie（r=2的基数树）：
  • 仅在出现分支的位置创建节点，无分支的连续比特序列合并到同一条边中
  • 边存储连续比特信息+子节点指针，节点数量远少于二进制前缀树
  • 查询时可一次性跳过一段连续比特，效率更高

内容的提问来源于stack exchange，提问作者markodeezy