在跳过列表中找到 k-th 元素 - 需要解释

Question

我们在大学学习跳过列表，我们必须在跳过列表中找到 k-th 元素。我还没有在互联网上找到任何关于这个的信息，因为 skiplist 并不是一个真正流行的数据结构。 W. Pugh 在他的原始文章中写道：
每个元素x都有一个索引pos(x)。我们在我们的不变量中使用这个值但不存储它。 header 的索引为零，第一个元素的索引为一，依此类推。与每个前向指针相关联的是该指针所经过的距离的测量值 fDistance：
x→fDistance[i] = pos(x→forward[i]) – pos(x).
请注意，1 级指针遍历的距离始终为 1，因此此处可能会以略微增加算法复杂度为代价实现一些存储经济。

SearchByPosition(list, k)
if k < 1 or k > size(list) then return bad-index
    x := list→header
    pos := 0
    -- loop invariant: pos = pos(x)
    for i := list→level downto 1 do
        while pos + x→fDistance[i] ≤ k do
            pos := pos + x→fDistance[i]
            x := x→forward[i]
return x→value

问题是，我仍然不明白这里发生了什么。我们如何在不存储元素的情况下知道元素的位置？如果我们不存储它，我们如何从 pos(x) 计算 fDistance 呢？如果我们从跳过列表的最高层开始，我们如何知道我们以这种方式跳过了第 0 层（或 1 层，无论如何最低层）上有多少个节点？

Answer 1

我假设您指的是如何在跳过列表中找到第 k 个最小（或最大）元素。我认为这是一个相当标准的假设，否则你必须澄清你的意思。

我将在这个答案中引用维基百科上的 GIF：https://en.wikipedia.org/wiki/Skip_list

假设您要查找 k = 5 最小的元素。

你从最高层开始（图中4）。从 30 到 NIL，您会跳过多少个元素？ 6（我们也算了30）。太过分了

下一层。有多少人从 30 跳过到 50？ 2：30 和 40。

所以我们将问题简化为找到 k = 5 - 2 = 3 最小元素，从 50 开始，级别为 3。

有多少人从 50 跳过到 NIL？ 4，太多了。

下一层。有多少人从 50 跳过到 70？ 2。现在在 2 层找到从 70 开始的 3 - 2 = 1 最小元素。

有多少人从 70 跳过到 NIL？ 2，太多了。

在 1 层从 70 到 90？ 1（本身）。所以答案是70.

因此您需要存储每个级别的每个节点跳过了多少个节点，并使用该额外信息以获得有效的解决方案。这似乎是 fDistance[i] 在您的代码中所做的。

在跳过列表中找到 k-th 元素 - 需要解释

Find k-th element in skiplist - explanation needed

algorithm

skip-lists