6

不确定问题应该在这里还是程序员（或其他一些 SE 站点），但我很好奇平衡二叉树和可索引跳过列表之间的相关差异。这个问题是在这个问题的背景下提出的。来自维基百科：

跳过列表是一种概率数据结构，似乎有可能取代平衡树作为许多应用程序选择的实现方法。跳过列表算法具有与平衡树相同的渐近预期时间界限，并且更简单、更快并且使用更少的空间。

跳过列表的空间要求不取决于层次结构的深度吗？并且二叉树不是更容易使用吗，至少对于搜索（在平衡 BST 中授予，插入和删除可能很棘手）？跳过列表还有其他优点/缺点吗？

4

4 回答 4

5

（您的问题的某些部分（易用性、简单性等）有点主观，我将在本文末尾回答。）

让我们看看空间使用情况。首先，假设您有一个具有 n 个节点的二叉搜索树。所需的总空间使用量是多少？好吧，每个节点都存储一些数据和两个指针。您可能还需要一些信息来维护余额信息。这意味着总空间使用量为

n * (2 * sizeof(指针) + sizeof(数据) + sizeof(余额信息))

因此，让我们考虑一个等效的跳过列表。您绝对正确，skiplist 使用的实际内存量取决于节点的高度，但我们可以讨论skiplist 使用的预期空间量。通常，您从 1 开始选择跳过列表中节点的高度，然后反复掷硬币，只要翻转正面就增加高度，并在翻转反面时停止。鉴于此设置，跳过列表中的预期指针数量是多少？

概率论的一个有趣结果是，如果您有一系列概率为 p 的独立事件，则在该事件发生之前您需要大约 1 / p 次试验（按预期）。在我们的抛硬币示例中，我们正在抛硬币直到它出现反面，并且由于硬币是一枚公平的硬币（正面朝上的概率为 50%），因此在我们反面之前所需的预期试验次数是 2。由于最后一次翻转结束了增长，因此一个节点在跳过列表中增长的预期次数为 1。因此，按照预期，我们预计一个平均节点中只有两个指针——一个初始指针和一个添加指针。这意味着预期的总空间使用量为

n * (2 * sizeof(指针) + sizeof(数据))

将此与平衡二叉搜索树中节点的大小进行比较。如果存储余额信息所需的空间量不为零，则跳过列表确实将使用（按预期）比平衡 BST 更少的内存。请注意，许多类型的平衡 BST（例如treap s）需要大量平衡信息，而其他类型（红/黑树、AVL 树）具有平衡信息，但可以将该信息隐藏在其指针的低位中，而其他（展开树）根本没有任何平衡信息。因此，这并不能保证获胜，但在许多情况下它会占用空间。

至于您关于简单性、易用性等的其他问题：这真的取决于。我个人发现在 BST 中查找元素的代码比在跳过列表中查找元素的代码要容易得多。然而，平衡 BST 中的旋转逻辑通常比跳过列表中的插入/删除逻辑复杂得多。试着看看你是否可以在不参考参考的情况下说出红/黑树中所有可能的旋转情况，或者看看你是否能记住伸展树中所有的 zig/zag 与 zag/zag 情况。从这个意义上说，记住从跳过列表中插入或删除的逻辑可能会更容易一些。

希望这可以帮助！

于 2013-04-01T17:44:33.837 回答
3

并且二叉树不是更容易使用吗，至少对于搜索（在平衡 BST 中授予，插入和删除可能很棘手）？

树是“更递归的”（树和子树），而 SkipLists 是“更迭代的”（数组中的级别）。当然，这取决于实现，但 SkipLists 在实际应用中也非常有用。

在树中搜索更容易，因为您不必在数组中迭代级别。

跳过列表还有其他优点/缺点吗？

  • SkipLists 更容易实现。这有点相对，但是实现一个全功能的 SkipList 比在 BinaryTree 中的删除和平衡操作更容易。

  • 树可以是持久的（更适合函数式编程）。

  • 从 SkipLists 中删除项目比二叉树中的内部节点更容易。

  • 将项目添加到二叉树更容易（保持平衡是另一个问题）

  • 二叉树是确定性的，因此更容易研究和分析它们。

我的提示：如果你有时间，你必须使用平衡二叉树。如果您的时间不多，请使用跳过列表。如果您没有时间，请使用图书馆。

于 2013-04-01T21:59:40.383 回答
3

到目前为止没有提到的是跳过列表对于并发操作可能是有利的。如果您阅读了由 Doug Lea 撰写的 ConcurrentSkipListMap 的源代码……请阅读评论。它提到：

对于搜索树，没有已知的有效的无锁插入和删除算法。索引节点的“向下”链接的不变性（与真实树中的可变“左”字段相反）使得仅使用 CAS 操作即可处理。

于 2014-11-13T20:00:44.143 回答
1

你是对的，这不是一个完美的论坛。

您引用的评论是由原始跳过列表论文的作者撰写的：不完全是一个公正的断言。已经 23 年了，红黑树似乎仍然比跳过列表更普遍。一个例外是redis 键值对数据库，它包括跳过列表作为其数据结构中的一个选项。

跳过列表非常酷。但是我在一般随机情况下能够展示的唯一空间优势是不需要存储平衡标志：每个值两位。这是假设层次结构足够密集以复制二叉树的性能。您可以将其归结为确定性的代价（副随机化）。SL 的一个很好的特性是您可以使用密度较低的层次结构来用恒定的速度因子换取空间。

旁注：如果您不需要按排序顺序遍历，您可以通过仅加密密钥来随机化不平衡二叉树（即使用非常简单的东西如 RC4 映射到伪随机密文），这并不经常讨论。这样的树实现起来绝对是微不足道的。

于 2013-04-01T17:41:12.780 回答