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

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

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

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

Построение

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

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

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

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

Псевдокод

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

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

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

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

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

   list build_lvl(list lvl)                   
       list next_lvl 
       node i = lvl.head.next.next                      
       node cur = next_lvl.head 
       while i $\neq$ null and i.next $\neq$ null
           cur.next = node(key, i, cur.next)                  // Конструктор node(key, down, next) возвращает новую вершину с ключом key, ссылками down на нижний и next на следующий элемент
           cur = cur.next
           i = i.next.next                                    // Переход к следующему чётному элементу
       return next_lvl 

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

   list skip_list(list l):
       list lvl                                               // Построение первого уровня
       node i = l.head
       node j = lvl.head
       while j $\neq$ l.tail
           i.next = node(j.key, null, j.next)
           i = i.next
           j = j.next
       while lvl.size > 2                     
           lvl = build_lvl(lvl)                       
       return lvl                                             // Возвращает ссылку на начало верхнего уровня

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

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

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

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

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

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

Псевдокод

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

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

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

   find(skip.head, key)

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

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

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

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

Псевдокод

Функция $\mathtt{insert}$ возвращаем ссылку на вставленный элемент в списке, в котором находится $\mathtt{res}$, или null, если на монете выпала «Решка».

   node insert(node res, K key)
       while res.next $\neq$ null and res.next.key < key
           res = res.next                                    
       node down_node
       if res.down = null
           down_node = null
       else
           down_node = insert(res.down, key)
       if down_node $\neq$ null or res.down = null                // Если выпал «Орёл» или мы находимся на первом уровне
           res.next = node(key, down_node, res.next)
           if random(0, 1) > 0.5                              // Бросок монеты
               return res.next
           return null
       return null

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

   function insert_element(list skip, K key)
       node res = insert(skip.head, key)
       if res $\neq$ null
           list lvl
           lvl.head.next = node(key, res, lvl.tail)
           skip = lvl

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

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

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

Псевдокод

Функция $\mathtt{delete}$ удаляет элемент $\mathtt{key}$ со всех уровней.

   function delete(node res, K key)
       while res.next $\neq$ null and res.next.key < key
           res = res.next
       if res.down $\neq$ null
           delete(res.down, key)
       if res.next $\neq$ null and res.next.key = key
           res.next = res.next.next

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

   delete(skip.head, key)

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

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

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

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

Применение

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

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

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

Задача:

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

Для решения данной задачи воспользуемся списком с пропусками. Когда нам приходит запрос первого типа, то мы просто добавляем числа $L$ и $R$ в список с пропусками (если какое-то из чисел уже было добавлено, то второй раз мы его не добавляем). После этого идём с верхнего уровня, и на каждом уровне мы ищем такие $l$ и $r$, что значение $l$ не больше $L$, а значение следующего за $l$ элемента уже больше $L$. Аналогично ищем такое же $r$, только относительно $R$. Если значения $l.next$ и $r$ лежат полностью внутри отрезка $[L, R]$, то к самому отрезку $[l.next, r]$ прибавляем $1$, а сам отрезок $[L, R]$ разбиваем на два и по отдельности прибавляем уже отрезки $[L, l.next.key - 1]$ и $[r.key + 1, R]$ (если для какого-то отрезка левая граница стала больше правой, то мы ничего не делаем). Допустим, что на каком-то уровне у нас получилось разделить отрезок $[L, R]$ на $3$ части. Но тогда на следующих уровнях мы будем уменьшать отрезок почти в два раза только с одной стороны, поскольку другая часть отрезка уже будет иметь точную границу. Итого время обработки запроса $O(\log{n})$.

Для запросов второго типа мы снова будем спускать с верхнего уровня до нижнего. На каждом уровне найдём тот элемент, значение которого не меньше точки $x$. Если такой элемент нашёлся, то прибавляем к ответу значение на отрезку между найденным элементом и следующим. Потом также спускаемся на один уровень вниз, если текущий уровень не был первым. Очевидно, что данный тип запросов мы обрабатываем за $O(\log{n})$.

См. также

• Список
• Рандомизированное бинарное дерево поиска
• Поисковые структуры данных
• 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