相关疑难解决方法(0)

虽然很难找到"基数树"的一致定义,但大多数公认的基数树定义表明它是一个压缩的前缀树.我正在努力理解的是在这种情况下术语"基数"的重要性.为什么压缩的前缀树如此命名(即Radix Tree),而非压缩的前缀树不称为Radix Tree？

根据libstdc ++文档的第 3点和第4点,PATRICIA尝试有两种类型的节点:

A(PATRICIA)trie类似于树,但有以下区别:

1. 它明确地将键视为一系列元素.例如,trie可以将字符串视为字符序列; 特里可以将数字视为一系列位.

2. 它不一定是二进制的.每个节点都有扇出n + 1,其中n是不同元素的数量.

3. 它仅在叶节点处存储值.

4. 内部节点具有以下属性:A)每个具有至少两个子节点,并且B)每个节点与其任何后代共享相同的前缀.

我一直在阅读的书(Algorithms in C,Part 1-4 by Robert Sedgewick)似乎描述了一个PATRICIA trie,只用n个节点存储n个值,使用内部节点存储值:

与DST一样,patricia尝试允许仅使用N个节点搜索树中的N个键....我们通过另一个简单的设备避免外部节点:我们将数据存储在内部节点中,并用链接指向外部节点的链接,这些链接指向trie中正确的内部节点

这里似乎有两个信仰阵营:

1. 一方面,我们有一个严格的,具体的定义(即Sedgewick,Knuth,Morrison,他们似乎都将PATRICIA专门描述为一个前缀压缩的二叉树,单向分支被淘汰); 和
2. 然后我们让那些人相信这个术语形成了一个松散的,含糊不清的定义,似乎更像是他们想要使用像"map","dictionary"或"trie"这样的词(它们实际上都是松散定义的,即libcs​​td ++文档).

我想我很担心资源的准确性.据我所知,由于公共前缀引入的问题,不可能只用N个节点表示一个树而不将其表示为二叉树(这似乎违反了libcs​​td ++ docs的第2点,而在处理变量时则指向第4点) -width keys),并且不会失去严格的单向分支的概念(通过使"叶子节点"和"子节点"的概念有些无效而违反第3点和第4点).这两个特性协同工作以消除"内部节点"的困境,这种困境会导致这些树使用多于N个节点(回想一下:N个项目只有N个节点).

这两组参考文献不能都是正确的; 相互排斥太多了.如果一个参考文献说PATRICIA是二元的而另一个参考文献说它可能不是,那么它们不能被认为是事实上正确的,这只是我在这里看到的一个不一致的例子.哪些参考文献是正确的？