为什么跳过列表必须在同一塔中保存重复的元素？-解网

问：

我目前正在学习跳过列表，我正在努力理解为什么一座塔在每个级别都包含相同元素的副本。我的直觉告诉我，这是多余的，并且可以在不复制插入期间塔内的元素的情况下实现跳过列表的相同概率质量。

考虑这个例子，从Goodrich，Tamassia和Mount的C++数据结构和算法中搜索键的跳过列表，其中访问的位置以蓝色突出显示： （这是一个视频，说明了搜索的每个步骤）50

这个跳过列表本身包含 37 个节点，其中 25 个是引用同一元素的重复节点。此外，搜索中的每个下拉列表都保证是相同的元素，如果在 S₀ 处，则为 NULL。所以我说，让我们去掉每个塔顶部下的重复项，而是让它们指向它们唯一可以遍历的节点。在这个跳过列表中，任何给定的搜索遍历都只能导致相同的键比较路径，所以我相信它可以像这样更有效地构建：

S_5:               -∞
                 /    \
S_4:           17      12
             /  |  \
S_3:       25  55   20
            |
S_2:       31
          /   \
S_1:    38     44
         |      |
S_0:    39     50

在这种结构中，我们可以从左到右比较每个子节点，如果，则下拉到该子节点，如果没有子节点满足该条件，则返回当前节点。我相信插入可以通过在每个级别掷硬币直到你得到反面并使用相同的标准插入子项来解决，我认为这将具有与原始跳过列表相似或相同的概率性质。desired_key >= child

我知道跳过列表应该是二叉搜索树的替代品，也许这可能只是一个效率较低的搜索树，但我仍然有一种唠叨的空间冗余感。您认为使用这种或类似方法可以在跳过列表中删除重复的键条目吗？

优化数据结构语言无关的空间复杂性跳过列表

该视频是跳过列表工作原理的一个很好的示例，但总的来说，它并不是跳过列表的一个特别好的例子。在实践中，跳过列表将包含数千甚至数百万个数据项，平均而言（假设在下一级添加链接的概率为 1/2），每个节点有两个链接。这使它具有与二叉搜索树相同的空间复杂性。经验证据表明，在查找过程中，跳过列表比平衡树更快，并且在某些情况下实际上使用更少的空间。对我来说，最重要的是，插入和删除跳过列表比维护平衡的二叉搜索树要简单得多，也快得多。

也就是说，如果你要拆除塔楼的下层，那么根本无法保证你能找到一个物品。你肯定需要保持塔的最低层。否则，就无法保证找到特定节点的方法。如果你没有塔的中间层，那么“跳进”功能就变得不那么有用了：你快速地跳到顶层，然后继续测试每个节点。

如果您担心空间（但同样，跳过列表实际上使用与平衡树相同的空间量），您可以随时使用不同的概率来添加下一级链接。正如我所说，1/2 很常见：当您插入一个节点时，您会创建最低级别的链接，并以 1/2 的概率将其添加到另一个级别。您可以将其更改为 1/4 或 1/7 或任何您喜欢的内容。这将减少列表所需的空间，但会减慢搜索时间。

上一个：是否依赖于尾调用（包括尾递归）编译器/实现？

下一个：为什么 Object 提供 equals 和 hash 代码方法？

为什么跳过列表必须在同一塔中保存重复的元素？

Why must skip lists hold duplicate elements within the same tower?

评论