Найти k-й элемент в списке пропусков - требуется пояснение

Question

Мы изучаем скиплисты в моем университете, и мы должны найти k-й элемент в скиплисте. Я не нашел ничего об этом в интернете, так как скип-лист не очень популярен. В. Пью в своей оригинальной статье писал:
Каждый элемент x имеет индекс pos (x). Мы используем это значение в наших инвариантах, но не храним его. Индекс заголовка равен нулю, индекс первого элемента равен единице и так далее. С каждым прямым указателем связано измерение 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

Проблема в том, что я до сих пор не понимаю, что здесь происходит. Как мы узнаем положения элементов, не сохраняя их? Как мы вычисляем fDistance из pos (x), если мы не храним его? Если мы перейдем с самого высокого уровня в списке пропусков, как мы узнаем, сколько узлов на уровне 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. Теперь найдите 3 - 2 = 1 наименьший элемент, начиная с 70 на уровне 2.

Сколько пропустили с 70 до NIL? 2, слишком много.

От 70 до 90 на уровне 1? 1 (само по себе). Таким образом, ответ 70.

Таким образом, вам нужно хранить количество пропущенных узлов для каждого узла на каждом уровне и использовать эту дополнительную информацию для получения эффективного решения. Похоже, именно это fDistance[i] делает в вашем коде.