algorithm - 如何在 Skip-List 中搜索元素

Question

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

我找到了采用 O(log n) 的已知算法，但这里是 O(log K)。

提前谢谢你

Answer 1

您需要扩充跳过列表，以便每个节点都有其“子树”中元素的计数(从其右下位置到其级别中的下一个节点的元素)。

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

一旦你有了这个元数据，你只需要进入一个级别，直到下一个级别的节点已经太靠右了。此时，向下一层。

---

顺便说一句，这个问题通过增强被称为动态订单统计。我从未在跳过列表中看到它，但您可以找到有关如何使用其他有序树执行此操作的链接的 gazoogles，这几乎是相同的想法。