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

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

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

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

Построение

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

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

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

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

Псевдокод

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

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

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

   struct node:
       node next, down
       K key

Также известно, что [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
       next_lvl.head.down = lvl.head
       next_lvl.tail.down = lvl.tail 
       node i = lvl.head.next.next                      
       node cur = next_lvl.head 
       while i [math]\neq[/math] null and i.next [math]\neq[/math] 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 

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

   list skip_list(list l):
       list lvl                                               // Построение первого уровня
       node i = l.head
       node j = lvl.head
       while j [math]\neq[/math] 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. Переместимся на один уровень вниз и перейти к шагу [math]2[/math]. Если мы уже на первом уровне — прекратим поиск и вернём ссылку на текущую вершину

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

Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет [math]\log{n}[/math] уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). Если же у нас будет [math]k[/math] уровней, тогда на каждом уровне в среднем будет в [math]n^{1/k}[/math] раз элементов больше, чем уровнем выше. В таком случае время поиска элемента [math]-[/math] [math]O(k \cdot n^{1/k})[/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. Переходим к следующему элементу списка пока значение следующей ячейки меньше ключа.
3. Если мы на первом уровне — вставляем элемент. Иначе спускаемся ниже и возвращаемся к шагу [math]2[/math]. Если нам вернули не null — вставляем элемент на текущем уровне тоже.
4. Кидаем монетку и если выпал «Орёл», то возвращаем ссылку на текущий элемент, иначе — null. Если мы были не на первом уровне и нам вернули null — возвращаем его без броска монетки.

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

Заметим, что вставка элемента [math]-[/math] поиск элемента и за [math]O(1)[/math] добавляем не более, чем в [math]k[/math] уровней элемент. Итого время работы [math]O(k \cdot n^{1/k})[/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.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 [math]\neq[/math] null or res.down = null                // Если выпал «Орёл» или мы находимся на первом уровне
           res.next = node(key, down_node, res.next)
           if coin_flip() = head                              // Если выпал «Орёл»
               return res.next
           return null
       return null

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

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

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

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

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

Псевдокод

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

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

Аналогично со вставкой удаление [math]-[/math] поиск элемента за [math]O(k \cdot n^{1/k})[/math] плюс удаление на каждом уровне за [math]O(1)[/math]. Итого [math]-[/math] [math]O(k \cdot n^{1/k})[/math].

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

   delete(skip.head, key)

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

Вместо честной монеты с распределением [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_{1/p} {n} \right)[/math] [math]([/math]на [math]i[/math]-ом уровне элементов будет почти в [math]\dfrac{1}{p}[/math] раз больше, чем на [math](i+1)[/math]-ом, значит на каждом уровне пройдём не более [math]\dfrac{1}{p}[/math] элементов, а уровней всего [math]\log_{1/p} {n}[/math][math])[/math].

Пусть у нас добавлено [math]n[/math] элементов. Найдём такое распределение [math]\left\{ p, q \right\}[/math], при котором функция [math]\dfrac{1}{x} \log_{1/x} {n}[/math] принимает минимальное значение. Производная этой функции равна [math]-\dfrac{\ln{n} \left( \ln {(1/x)} - 1 \right)}{x^2 \ln^2{(1/x)}}[/math]. При [math]x = \dfrac{1}{e}[/math] производная равна нулю, вторая производная в точке [math]x_0 = \dfrac{1}{e}[/math] больше [math]0[/math], значит [math]x_0[/math] [math]-[/math] точка минимума. Значит при распределении [math]\left\{ \dfrac{1}{e}, \dfrac{e - 1}{e} \right\}[/math] время поиска меньше всего. Но не стоит забывать, что это лишь теоретическая оценка и в действительности придумать источник с распределением [math]\left\{ \dfrac{1}{e}, \dfrac{e - 1}{e} \right\}[/math] почти невозможно, поэтому на практике лучше всего использовать честную монету.

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

• [math]\{0, 1\}[/math] — [math]O(n)[/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]l[/math] меньше [math]L[/math], а значение следующего за [math]l[/math] элемента уже не меньше [math]L[/math]. Аналогично ищем такое же [math]r[/math], только относительно [math]R[/math]. Если значения [math]l.next[/math] и [math]r[/math] лежат полностью внутри отрезка [math][L, R][/math], то к самому отрезку [math][l.next, r][/math] прибавляем [math]1[/math], а сам отрезок [math][L, R][/math] разбиваем на три [math][L, l.next.key - 1][/math], [math][l.next.key, r.key][/math] и [math][r.key + 1, R][/math] и по отдельности решаем задачу уже для полученных отрезков (если для какого-то отрезка левая граница стала больше правой, то мы ничего не делаем). Допустим, что на каком-то уровне у нас получилось разделить отрезок [math][L, R][/math] на [math]3[/math] части. Но тогда на следующих уровнях мы будем уменьшать отрезок почти в два раза только с одной стороны, поскольку левая или правая часть отрезка будет равна [math]l.next.key[/math] или [math]r.key[/math]. Итого время обработки запроса [math]O(\log{n})[/math].

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

См. также

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

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

• Википедия — списки с пропусками
• 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