如何在Skip-List中搜索元素

Question

我正在寻找一种在跳跃列表中找到给定元素x的方法，它是列表中的第k个元素(在它之前有k-1个元素)。算法的期望时间应该是O(log )

我找到了已知的算法，它需要O(log )，但在这里它是O(log )。

提前感谢你

Answer 1

您需要增加skiplist，以便每个节点都有其“子树”中的元素计数(元素位于其向下右侧的位置，直到其级别中的下一个节点)。

很容易看出，您可以在不改变列表操作的复杂性的情况下增加此信息。

一旦您有了这个元数据，您只需要在下一个级别上的节点已经太靠右的点上就可以了。此时，再往下走一级。

顺便说一下，这个问题被称为通过增强的动态顺序统计量。我从来没有见过跳跃列表，但是你可以找到关于如何使用其他有序树的链接，而且它的想法几乎是一样的。