混淆关于PATRICIA

Question

根据点3和的libstdc++ documentation 4，PATRICIA尝试有两种类型的节点：

A（PATRICIA）线索类似于树，但具有下列 差异：

1. 它明确地将键视为一系列元素。例如，特里可以将字符串视为一系列字符;特里可以将一个 号码视为一个比特序列。

2. 它不是（必然）是二​​元的。每个节点都有扇出n + 1，其中n是不同元素的数量。

3. 它只存储叶节点的值。

4. 内部节点具有以下特性：A）每个至少有两个孩子; B）每个孩子与其任何一个孩子都有相同的前缀 后代。

这本书我一直在读（算法在C，1-4部分由罗伯特·塞奇威克）似乎描述PATRICIA线索存储与仅n个节点的n值，使用内部节点的存储值：

与DST类似，patricia试图允许在仅有 N个节点的树中搜索N个密钥。 ......我们通过另一个简单的装置，避免外部节点：在内部节点，我们 存储数据，并与 链接指向向上返回到正确的内部节点线索

我猜我更换链接到外部节点我担心我的资源的准确性（编辑：...并且这些并不是这个话题中唯一引起争议的两个参考）。哪些参考文献是正确的？

Answer 1

我继续寻找从过去的有信誉的来源明确的定义，以确认我所怀疑的，我正在写，提供我的发现。也许最显著是官方给出定义PATRICIA，由DR莫里森1968s月出版的“ACM学报”：

PATRICIA从“一库自动机” [3]等研究中发展。 ... 在这个进化的早期，它决定字母应该是 限制为二进制。一个强烈影响这个决定的定理是以另一种形式归因于欧拉的定理。定理 指出，如果字母表是二进制的，那么分支的数量是 恰好比结束的数量少一个。推论表明，随着图书馆的发展，每一个新的结局都会带着它进入图书馆，其中 恰恰就是一个新的分支，而每个分支恰好有两个出口。这些事实在索引的存储分配中非常有用。他们 意味着所需的总空间完全被 数字结尾的确定，以及所有所需的存储实际上会被使用。

这肯定与libstdC++参考的第2和第3点相矛盾。本文中还有更多的证据，例如具体的算法细节，但上面的引用应该足够了。

似乎没有从在塞奇威克报价官方描述的任何偏差，但是。基于此，libstdC++资源当然不如Sedgewick资源有效。

Answer 2

虽然这两个定义看起来都是正确的，但第一个更详细，对我来说似乎更好。也看看this answer，我试图描绘一个帕特里夏和普通Trie之间的区别。