没有随机化的跳表？

Question

没有随机化的跳表？

randomskip-lists

7

我阅读了一些关于跳表的内容，并正在实现它。但是有一件事情到目前为止我还没有完全理解，那就是为什么跳表是随机的？在我找到的所有资料中，跳表都使用随机数来决定插入项目的级别。难道不能计算出最优解吗？或者不能说“每四个项目”应该插入到上一级吗？

- API-Beast

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- pjs · Accepted Answer

Skip lists可以被确定性地构建，例如为了最小化摊销访问成本。然而，对于任何确定性的构建方法，更高级别的列表条目集总是已知的，因此很容易构造一组“敌对”的删除操作，使性能退化到O(n)。通过随机构建，仍然存在最坏情况的删除集，但对于任何相当大的列表，仅凭偶然发现最坏情况的删除序列的可能性是微乎其微的。