algorithm - 在跳过列表中查找第 k 个元素 - 需要解释

Question

我们在我的大学学习跳过列表，我们必须在跳过列表中找到第 k 个元素。我还没有在互联网上找到任何关于这个的信息，因为 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 - 跳跃列表中第 th 最小(或最大)的元素。我认为这是一个相当标准的假设，否则你必须澄清你的意思。

我将在这个答案中引用维基百科上的 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 .现在找到 3 - 2 = 1从 70 开始的最小元素在水平 2 .

从 70 中跳过了多少至 NIL ？ 2 , 太多了。

来自 70至 90在水平 1 ？ 1 (本身)。所以答案是70 .

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