根据libstdc++ documentation的第3点和第4点，PATRICIA尝试有两种类型的节点：
A（PATRICIA）trie类似于树，但有以下区别：它明确地将键视为一系列元素 . 例如，trie可以将字符串视为一系列字符;特里可以将数字视为一系列位 . 它不一定是二进制的 . 每个节点都有扇出n 1，其中n是不同元素的数量 . 它仅在叶节点处存储值 . 内部节点具有以下属性：A）每个具有至少两个子节点，并且B）每个节点与其任何后代共享相同的前缀 .
我一直在阅读的书（Algorithms in C，Part 1-4 by Robert Sedgewick）似乎描述了一个PATRICIA trie，只用n个节点存储n个值，使用内部节点存储值：
与DST一样，patricia尝试允许仅使用N个节点搜索树中的N个键 . ...我们通过另一个简单的设备避免外部节点：我们将数据存储在内部节点中，并用链接指向外部节点的链接，这些链接指向trie中正确的内部节点
这里似乎有两个信仰阵营：
-
一方面，我们有一个严格的，具体的定义（即Sedgewick，Knuth，Morrison，他们似乎都将PATRICIA专门描述为一个前缀压缩的二叉树，单向分支被消除）;和
-
然后我们让那些人相信这个术语形成一个松散的，模糊的定义，看起来更像他们想要使用像"map"，"dictionary"或"trie"这样的词（它们实际上都是松散定义的，即libcstd文档） .
我想我很担心资源的准确性 . 据我所知，由于公共前缀引入的问题，不可能只用N个节点表示一个树而不将其表示为二叉树（这似乎违反了libcstd docs的第2点，而在处理变量时则指向第4点） -width keys），并且不会失去严格的单向分支的概念（通过使“叶子节点”和“子节点”的概念有些无效而违反第3点和第4点） . 这两个特性协同工作以消除“内部节点”的困境，这种困境会导致这些树使用多于N个节点（回想一下：N个项目只有N个节点） .
这两组参考文献不能都是正确的;相互排斥太多了 . 如果一个参考文献说PATRICIA是二元的而另一个参考文献说它可能不是，那么它们不能被认为是事实上正确的，这只是我在这里看到的一个不一致的例子 . 哪些参考文献是正确的？
2 回答
我继续从过去的信誉来源中寻找一个具体的定义，以确认我所怀疑的内容，并且我写信是为了提供我的发现 . 也许最重要的是定义PATRICIA的官方文件，由DR Morrison于1968年10月出版的“ACM杂志”：
这肯定与libstdc引用的第2点和第3点相矛盾 . 本文还有其他证据，例如特定的算法细节，但上面的引用应该足够了 .
但是，Sedgewick报价中的官方描述似乎没有任何偏差 . 基于此，libstdc资源肯定不如Sedgewick资源有效 .
虽然这两个定义似乎都是正确的，但第一个定义更详细，对我来说似乎更好 . 另外看看this answer，我试图描绘Patricia和普通Trie之间的区别 .