Список с пропусками

Пример списка с пропусками

Список с пропусками (англ. skip list) — вероятностная структура данных, позволяющая в среднем за [math]O(\log(n))[/math] времени выполнять операции добавления, удаления и поиска элементов.

Список с пропусками состоит из нескольких уровней, на каждом из которых находится отсортированный связный список. На самом нижнем (первом) уровне располагаются все элементы. Дальше около половины элементов в таком же порядке располагаются на втором, почти четверть [math]-[/math] на третьем и так далее, но при этом известно, что если элемент расположен на уровне [math]i[/math], то он также расположен на всех уровнях с номерами меньших [math]i[/math].

Построение

Односвязный отсортированный список

Получившийся список с пропусками

Допустим, что нам задан односвязный отсортированный список и мы хотим построить на его основе список с пропусками, позволяющий в среднем за [math]O(\log{n})[/math] времени выполнять операции добавления, удаления и поиска элементов.

На самом нижнем уровне списка с пропусками мы расположим исходный список. На втором уровне [math]-[/math] всё элементы с чётными номерами, причём каждый элемент будет ссылаться на соответствующий ему элемент на нижнем уровне. Таким же образом построим и третий уровень, куда будем добавлять только те элементы, номера которых кратны четырём. Аналогичным образом построим и последующие уровни.

Псевдокод

Каждый уровень списка с пропусками содержит отсортированный односвязный список, у которое есть начало [math]\mathtt{head}[/math] и конец [math]\mathtt{tail}[/math]. Для выполнения операций на списке с пропусками необходимо передавать в качестве аргумента ссылку на начало односвязного списка, расположенного на самом верхнем уровне.

Элементы односвязного списка [math]-[/math] вершины [math]\mathtt{node}[/math], у которых есть [math]3[/math] поля:

• [math]\mathtt{next}[/math] [math]-[/math] ссылка на следующий элемент списка
• [math]\mathtt{key}[/math] [math]-[/math] ключ, который хранится в данной вершине
• [math]\mathtt{down}[/math] [math]-[/math] ссылка на соответственный элемент, лежащий уровнем ниже

Также известно, что [math]\mathtt{head{.}key} = -\infty \ [/math] и [math]\mathtt{tail{.}key} = \infty[/math].

Функция [math]\ \mathtt{build\_lvl} \ [/math] возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.

   list build_lvl (list lvl)                   // Отсеивание нечётных элементов
       list next_lvl 
       node i = lvl.head                      
       while (i != null) and (i != lvl.tail)
           next_lvl.push_back(node(i.key, i))  // Конструктор node(key, down) возвращает новую вершину с ключом key и ссылкой down на соответствующую вершину предыдущего уровеня
           i = i.next.next                     // Переход к следующему чётному элементу
       return next_lvl 

Функция [math]\ \mathtt{skip\_list} \ [/math] принимает в качестве аргумента односвязный отсортированный список и возвращает новый список с пропусками, построенный на его основе.

   list skip_list (list l):
       list lvl = build_lvl(l)                // Построение первого уровня
       while lvl.size > 2                     // Добавление следующих уровней; последний содержит не более двух элементов
           lvl = build_lvl(lvl)                       
       return lvl                             // Возвращает ссылку на начало верхнего уровня

Операции над структурой

Поиск элемента

Пример поиска числа [math]8[/math]

Алгоритм поиска элементе в списке с пропусками состоит из следующих операций:

1. Начинаем поиск элемента в самом верхнем уровне
2. Переходим к следующему элементу списка, пока значение в следующей ячейке меньше
3. Переместиться на один уровень вниз и перейти к шагу [math]2[/math]. Если мы уже на первом уровне [math]-[/math] прекратить поиск и вернуть ссылку на текущую вершину

В конце алгоритма функция вернёт элемент, значение которого не меньше ключа [math]\mathtt{key}[/math] или ссылку на конец списка на первом уровне.

Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет [math]\log{n}[/math] уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). Уровней всего [math]\log{n}[/math], откуда вытекает оценка времени поиска элемента в [math]O(\log{n})[/math].

Псевдокод

Функция [math]\mathtt{find}[/math] возвращает ссылку на элемент, значение которого не меньше [math]\mathtt{key}[/math]. В случае, если все элементы в списке с пропусками меньше [math]\mathtt{key}[/math], то возвращается ссылка на конец списка с пропусками.

   T find (node res, K key)
       while res.key < key                                        // Пока значение вершины меньше ключа
           res = res.next                                         // Перейдём к следующей вершине в текущем уровне
       if res.down = null                                         // Если мы находимся на первом уровне
           return res                                             // Мы нашли искомый элемент
       return find(res.down, key)                                 // Иначе спустимся на один уровень ниже

Для того, чтобы найти элемент с ключом [math]\mathtt{key}[/math] в списке с пропусками [math]\mathtt{skip}[/math] необходимо запустить [math]\mathtt{find}[/math] следующим образом

   find(skip.head, key)

Вставка элемента

Алгоритм вставки элементов в список с пропусками состоит из следующих шагов:

1. Начинаем вставку на самом верхнем уровне
2. Пока следующих элемент следующего элемента меньше ключа [math]-[/math] идём по списку вправо.
3. Если мы на первом уровне [math]-[/math] вставляем элемент. Иначе спускаемся ниже и возвращаемся к шагу [math]2[/math].
4. Кидаем монетку и если выпал «Орёл», то возвращаем ссылку на текущий элемент, иначе [math]-[/math] null. Если мы были не на первом уровне и нам вернули null [math]-[/math] возвращаем его без броска монетки.

Отдельно стоит обработать случай, когда вставка нового элемента увеличивает число уровней. Тогда необходимо создать ещё один отсортированный список, в котором будет всего один текущий элемент, и не забыть присвоить списку с пропусками новую ссылку на верхний уровень. Будем считать, что вставка каждого нового элемента увеличивает число уровней не более, чем на один.

Псевдокод

Функция [math]\mathtt{insert}[/math] возвращаем ссылку на вставленный элемент в списке, в котором находится [math]\mathtt{res}[/math], или null, если на монете выпал не «Орёл».

   node insert (node res, K key)
       while res.next [math]\neq[/math] null and res.next.next [math]\neq[/math] null
           res = res.next
       if res.down = null
           res.next = node(key, null, res.next)
           if random(0, 1) > 0.5
               return res.next
           return null
       node i = insert(res.down, key)
       if i [math]\neq[/math] null
           res.next = node(key, i, res.next)
           if random(0, 1) > 0.5
               return res.next
           return null
       return null

Для того, чтобы вставить элемент с ключом [math]\mathtt{key}[/math] в список с пропусками [math]\mathtt{skip}[/math] необходимо вызвать следующую функцию

Удаление элемента

Алгоритм удаления элемента выглядит следующим образом:

1. Начинаем удалять элемент с верхнего уровня
2. Если мы на первом уровне и нашли элемент [math]-[/math] то просто удаляем элемент
3. Иначе спускаемся ниже и также удаляем элемент с текущего уровня, если он есть

Использование нечестной монеты

Вместо честной монеты с распределением [math]\left\{\dfrac{1}{2}, \ \dfrac{1}{2}\right\}[/math] можно взять в качестве случайного источника нечестную монету с распределением [math]\{p,q\}[/math] (с вероятностью [math]p[/math] выпадает «Орёл»). Тогда математическим ожиданием количества элементов на уровне [math]k[/math] будет [math]n \cdot p^k[/math]. Время поиска будет равно [math]O\left( \dfrac{1}{p} \log_{\frac{1}{p}} {n} \right)[/math] (на [math]i[/math]-ом уровне элементов будет почти в [math]\dfrac{1}{p}[/math] раз больше, чем на [math](i+1)[/math]-ом, значит на каждом уровне пройдём не более [math]\dfrac{1}{p}[/math] элементов, а уровней всего [math]\log_{\frac{1}{p}} {n}[/math]).

Для крайних распределений:

• [math]\{0, 1\}[/math] — [math]O(n)[/math] [math]-[/math] поиск, добавление и удаления элемента, поскольку мы вместо нескольких списков используем по факту один.
• [math]\{1, 0\}[/math] — зависит от реализации алгоритма. Если при каждой вставке у нас образуется не более одного уровня, то количество уровней будет равным [math]n[/math], значит время поиска будет равным [math]O(n)[/math].

Применение

Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ.

• Быстрая вставка элемента, поскольку не требуется каким-либо образом изменять другие элементы (только предыдущий элемент)
• Проще реализовать, чем сбалансированные деревья или хеш-таблицы
• Следующий элемент достаётся за [math]O(1)[/math] (при условии, что у нас есть ссылка не текущий)
• Легко модифицировать под различные задачи

Нахождение всех интервалов, покрывающих данную точку

Задача:

Поступают запросы двух видов: Добавить интервал [math][L, R][/math] Для заданной точки [math]x[/math] вычислить количество интервалов, которые её покрывают.

Для решения данной задачи воспользуемся списком с пропусками. Когда нам приходит запрос первого типа, то мы просто добавляем числа [math]L[/math] и [math]R[/math] в список с пропусками (если какое-то из чисел уже было добавлено, то второй раз мы его не добавляем), а также идём с самого верхнего уровня и до нижнего и если два элемента на каком-либо уровне находятся между [math]L[/math] и [math]R[/math], то прибавляем [math]1[/math] к отрезку, иначе спускаемся вниз. Когда нам приходит запрос второго типа [math]-[/math] на каждом уровне находим такие два элемента, что [math]x[/math] лежит между ними, и к ответу прибавляем значение на данном отрезке. Итого оба запросы мы выполняем за [math]O(\log{n})[/math].

См. также

• Список
• Рандомизированное бинарное дерево поиска
• Поисковые структуры данных
• Skip quadtree
• Skip graph — структура данных, основанная на списке с пропусками

Источники информации

• Википедия — списки с пропусками
• Wikipedia — skip list
• igoro.com — Skip lists are fascinating
• ticki.github.io — Skip Lists: Done Right
• Eric N. Hanson — A Data Structure for Finding All Intervals That Overlap a Point стр. 155-164