Список с пропусками — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Псевдокод)
м (Использование нечестной монеты)
(не показано 26 промежуточных версий этого же участника)
Строка 15: Строка 15:
 
====Псевдокод====
 
====Псевдокод====
  
Каждый уровень списка с пропусками содержит отсортированный односвязный список, у которого есть начало <tex>\mathtt{head}</tex> и конец <tex>\mathtt{tail}</tex>. Для выполнения операций на списке с пропусками необходимо передавать в качестве аргумента ссылку на начало односвязного списка, расположенного на самом верхнем уровне.
+
Каждый уровень списка с пропусками содержит отсортированный односвязный список, у которого есть начало <tex>\mathtt{head} \ </tex> и конец <tex>\mathtt{tail}</tex>. Для выполнения операций на списке с пропусками необходимо передавать в качестве аргумента ссылку на начало односвязного списка, расположенного на самом верхнем уровне.
  
 
Элементы односвязного списка — вершины <tex>\mathtt{node}</tex>, у которых есть <tex>3</tex> поля:
 
Элементы односвязного списка — вершины <tex>\mathtt{node}</tex>, у которых есть <tex>3</tex> поля:
* <tex>\mathtt{next}</tex> — ссылка на следующий элемент списка
+
* <tex>\mathtt{next}</tex> — ссылка на следующий элемент списка на данном уровне
 
* <tex>\mathtt{key}</tex> — ключ, который хранится в данной вершине
 
* <tex>\mathtt{key}</tex> — ключ, который хранится в данной вершине
 
* <tex>\mathtt{down}</tex> — ссылка на соответственный элемент, лежащий уровнем ниже
 
* <tex>\mathtt{down}</tex> — ссылка на соответственный элемент, лежащий уровнем ниже
  
Также известно, что <tex>\mathtt{head{.}key} = -\infty \ </tex> и <tex>\mathtt{tail{.}key} = \infty</tex>.
+
    '''struct''' node:
 +
        '''node''' next, down
 +
        '''K''' key
 +
 
 +
Также известно, что <tex>\mathtt{head{.}key} = -\infty \ </tex> и <tex>\mathtt{tail{.}key} = \infty</tex>,
  
 
Функция <tex>\ \mathtt{build\_lvl} \ </tex> возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.
 
Функция <tex>\ \mathtt{build\_lvl} \ </tex> возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.
  
 
     '''list''' build_lvl('''list''' lvl)                   
 
     '''list''' build_lvl('''list''' lvl)                   
         '''list''' next_lvl  
+
         '''list''' next_lvl
 +
        next_lvl.head.down = lvl.head
 +
        next_lvl.tail.down = lvl.tail
 
         '''node''' i = lvl.head.next.next                       
 
         '''node''' i = lvl.head.next.next                       
 
         '''node''' cur = next_lvl.head  
 
         '''node''' cur = next_lvl.head  
Строка 39: Строка 45:
  
 
     '''list''' skip_list('''list''' l):
 
     '''list''' skip_list('''list''' l):
         '''list''' lvl = l                                          <font color=darkgreen>// Построение первого уровня</font>
+
         '''list''' lvl                                               <font color=darkgreen>// Построение первого уровня</font>
 +
        '''node''' i = l.head
 +
        '''node''' j = lvl.head
 +
        '''while''' j <tex>\neq</tex> l.tail
 +
            i.next = node(j.key, ''null'', j.next)
 +
            i = i.next
 +
            j = j.next
 
         '''while''' lvl.size > 2                     
 
         '''while''' lvl.size > 2                     
 
             lvl = build_lvl(lvl)                       
 
             lvl = build_lvl(lvl)                       
Строка 46: Строка 58:
 
==Операции над структурой==
 
==Операции над структурой==
 
===Поиск элемента===
 
===Поиск элемента===
 
[[Файл:SkipListSearch.png|thumb|600px|Пример поиска числа <tex>8</tex>]]
 
 
 
Алгоритм поиска элемента в списке с пропусками состоит из следующих операций:
 
Алгоритм поиска элемента в списке с пропусками состоит из следующих операций:
 
# Начинаем поиск элемента в самом верхнем уровне
 
# Начинаем поиск элемента в самом верхнем уровне
Строка 56: Строка 65:
 
В конце алгоритма функция вернёт элемент, значение которого не меньше ключа <tex>\mathtt{key}</tex> или ссылку на конец списка на первом уровне.
 
В конце алгоритма функция вернёт элемент, значение которого не меньше ключа <tex>\mathtt{key}</tex> или ссылку на конец списка на первом уровне.
  
Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет <tex>\log{n}</tex> уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). Уровней всего <tex>\log{n}</tex>, откуда вытекает оценка времени поиска элемента в <tex>O(\log{n})</tex>.
+
Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет <tex>\log{n}</tex> уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). Если же у нас будет <tex>k</tex> уровней, тогда на каждом уровне в среднем будет в <tex>n^{1/k}</tex> раз элементов больше, чем уровнем выше. В таком случае время поиска элемента <tex>-</tex> <tex>O(k \cdot n^{1/k})</tex>.
  
 
====Псевдокод====
 
====Псевдокод====
Строка 77: Строка 86:
 
# Начинаем вставку на самом верхнем уровне
 
# Начинаем вставку на самом верхнем уровне
 
# Переходим к следующему элементу списка пока значение следующей ячейки меньше ключа.
 
# Переходим к следующему элементу списка пока значение следующей ячейки меньше ключа.
# Если мы на первом уровне — вставляем элемент. Иначе спускаемся ниже и возвращаемся к шагу <tex>2</tex>.
+
# Если мы на первом уровне — вставляем элемент. Иначе спускаемся ниже и возвращаемся к шагу <tex>2</tex>. Если нам вернули не ''null'' — вставляем элемент на текущем уровне тоже.
 
# Кидаем монетку и если выпал «Орёл», то возвращаем ссылку на текущий элемент, иначе — ''null''. Если мы были не на первом уровне и нам вернули ''null'' — возвращаем его без броска монетки.
 
# Кидаем монетку и если выпал «Орёл», то возвращаем ссылку на текущий элемент, иначе — ''null''. Если мы были не на первом уровне и нам вернули ''null'' — возвращаем его без броска монетки.
  
Отдельно стоит обработать случай, когда вставка нового элемента увеличивает число уровней. Тогда необходимо создать ещё один отсортированный список, в котором будет всего один текущий элемент, и не забыть присвоить списку с пропусками новую ссылку на верхний уровень. Будем считать, что вставка каждого нового элемента увеличивает число уровней не более, чем на один.
+
Отдельно стоит обработать случай, когда вставка нового элемента увеличивает число уровней. Тогда необходимо создать ещё один отсортированный список, в котором будет всего один текущий элемент, и не забыть присвоить списку с пропусками новую ссылку на верхний уровень. Будем считать, что вставка каждого нового элемента увеличивает число уровней не более чем на один.
 +
 
 +
Заметим, что вставка элемента <tex>-</tex> поиск элемента и за <tex>O(1)</tex> добавляем не более, чем в <tex>k</tex> уровней элемент. Итого время работы <tex>O(k \cdot n^{1/k})</tex>.
  
 
====Псевдокод====
 
====Псевдокод====
Функция <tex>\mathtt{insert}</tex> возвращаем ссылку на вставленный элемент в списке, в котором находится <tex>\mathtt{res}</tex>, или ''null'', если на монете выпала «Решка».
+
Функция <tex>\mathtt{insert} \ </tex> возвращаем ссылку на вставленный элемент в списке, в котором находится <tex>\mathtt{res}</tex>, или ''null'', если на монете выпала «Решка».
  
 
     '''node''' insert('''node''' res, '''K''' key)
 
     '''node''' insert('''node''' res, '''K''' key)
Строка 93: Строка 104:
 
         '''else'''
 
         '''else'''
 
             down_node = insert(res.down, key)
 
             down_node = insert(res.down, key)
         '''if''' down_node <tex>\neq</tex> ''null''
+
         '''if''' down_node <tex>\neq</tex> ''null'' '''or''' res.down = ''null''                <font color=darkgreen>// Если выпал «Орёл» или мы находимся на первом уровне</font>
 
             res.next = node(key, down_node, res.next)
 
             res.next = node(key, down_node, res.next)
             '''if''' random(0, 1) > 0.5                             <font color=darkgreen>// Бросок монеты</font>
+
             '''if''' coin_flip() = ''head''                             <font color=darkgreen>// Если выпал «Орёл»</font>
 
                 '''return''' res.next
 
                 '''return''' res.next
 
             '''return''' ''null''
 
             '''return''' ''null''
Строка 115: Строка 126:
 
# Если элемент существует на данном уровне — удаляем его с этого уровня. Если мы не на первом уровне, то удаляем элемент ещё с нижнего уровня.
 
# Если элемент существует на данном уровне — удаляем его с этого уровня. Если мы не на первом уровне, то удаляем элемент ещё с нижнего уровня.
 
====Псевдокод====
 
====Псевдокод====
 +
Функция <tex>\mathtt{delete}</tex> удаляет элемент <tex>\mathtt{key}</tex> со всех уровней.
 +
 
     '''function''' delete('''node''' res, '''K''' key)
 
     '''function''' delete('''node''' res, '''K''' key)
 
         '''while''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.key < key
 
         '''while''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.key < key
Строка 121: Строка 134:
 
             delete(res.down, key)
 
             delete(res.down, key)
 
         '''if''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.key = key
 
         '''if''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.key = key
             res.next = res.next.next;
+
             res.next = res.next.next
 +
 
 +
Аналогично со вставкой удаление <tex>-</tex> поиск элемента за <tex>O(k \cdot n^{1/k})</tex> плюс удаление на каждом уровне за <tex>O(1)</tex>. Итого <tex>-</tex> <tex>O(k \cdot n^{1/k})</tex>.
 +
 
 +
Для того, чтобы удалить элемент <tex>\mathtt{key}</tex> из списка с пропусками <tex>\mathtt{skip}</tex>, необходимо вызвать функцию <tex>\mathtt{delete} \ </tex> следующим образом:
 +
 
 +
    delete(skip.head, key)
  
 
==Использование нечестной монеты==
 
==Использование нечестной монеты==
Вместо честной монеты с распределением <tex>\left\{\dfrac{1}{2}, \ \dfrac{1}{2}\right\}</tex> можно взять в качестве случайного источника нечестную монету с распределением <tex>\{p,q\}</tex> (с вероятностью <tex>p</tex> выпадает «Орёл»). Тогда математическим ожиданием количества элементов на уровне <tex>k</tex> будет <tex>n \cdot p^k</tex>. Время поиска будет равно <tex>O\left( \dfrac{1}{p} \log_{\frac{1}{p}} {n} \right)</tex> <tex>(</tex>на <tex>i</tex>-ом уровне элементов будет почти в <tex>\dfrac{1}{p}</tex> раз больше, чем на <tex>(i+1)</tex>-ом, значит на каждом уровне пройдём не более <tex>\dfrac{1}{p}</tex> элементов, а уровней всего <tex>\log_{\frac{1}{p}} {n}</tex><tex>)</tex>.  
+
Вместо честной монеты с распределением <tex>\left\{\dfrac{1}{2}, \ \dfrac{1}{2}\right\}</tex> можно взять в качестве случайного источника нечестную монету с распределением <tex>\{p,q\}</tex> (с вероятностью <tex>p</tex> выпадает «Орёл»). Тогда математическим ожиданием количества элементов на уровне <tex>k</tex> будет <tex>n \cdot p^k</tex>. Время поиска будет равно <tex>O\left( \dfrac{1}{p} \log_{1/p} {n} \right)</tex> <tex>(</tex>на <tex>i</tex>-ом уровне элементов будет почти в <tex>\dfrac{1}{p}</tex> раз больше, чем на <tex>(i+1)</tex>-ом, значит на каждом уровне пройдём не более <tex>\dfrac{1}{p}</tex> элементов, а уровней всего <tex>\log_{1/p} {n}</tex><tex>)</tex>.
 +
 
 +
Пусть у нас добавлено <tex>n</tex> элементов. Найдём такое распределение <tex>\left\{ p, q \right\}</tex>, при котором функция <tex>\dfrac{1}{x} \log_{1/x} {n}</tex> принимает минимальное значение. Производная этой функции равна <tex>-\dfrac{\ln{n} \left( \ln {(1/x)} - 1 \right)}{x^2 \ln^2{(1/x)}}</tex>. При <tex>x = \dfrac{1}{e}</tex> производная равна нулю, вторая производная в точке <tex>x_0 = \dfrac{1}{e}</tex> больше <tex>0</tex>, значит <tex>x_0</tex> <tex>-</tex> точка минимума. Значит при распределении <tex>\left\{ \dfrac{1}{e}, \dfrac{e - 1}{e} \right\}</tex> время поиска меньше всего. Но не стоит забывать, что это лишь теоретическая оценка и в действительности придумать источник с распределением <tex>\left\{ \dfrac{1}{e}, \dfrac{e - 1}{e} \right\}</tex> почти невозможно, поэтому на практике лучше всего использовать честную монету.
  
 
Для крайних распределений:
 
Для крайних распределений:
Строка 138: Строка 159:
 
* Легко модифицировать под различные задачи
 
* Легко модифицировать под различные задачи
  
===Нахождение всех интервалов, покрывающих данную точку===
+
===Нахождение всех отрезков, покрывающих данную точку===
  
 
{{Задача
 
{{Задача
 
|definition = Пусть у нас есть запросы двух видов:
 
|definition = Пусть у нас есть запросы двух видов:
 
# Добавить отрезок <tex>[L, R]</tex>
 
# Добавить отрезок <tex>[L, R]</tex>
# Для заданной точки <tex>x</tex> вычислить количество интервалов, которые её покрывают.  
+
# Для заданной точки <tex>x</tex> вычислить количество отрезков, которые её покрывают.  
 
Необходимо для каждого запроса второго типа вывести ответ.
 
Необходимо для каждого запроса второго типа вывести ответ.
 
}}
 
}}
  
Для решения данной задачи воспользуемся списком с пропусками. Когда нам приходит запрос первого типа, то мы просто добавляем числа <tex>L</tex> и <tex>R</tex> в список с пропусками (если какое-то из чисел уже было добавлено, то второй раз мы его не добавляем). После этого идём с верхнего уровня, и на каждом уровне мы ищем такие <tex>l</tex> и <tex>r</tex>, что значение <tex>l</tex> не больше <tex>L</tex>, а значение следующего за <tex>l</tex> элемента уже больше <tex>L</tex>. Аналогично ищем такое же <tex>r</tex>, только относительно <tex>R</tex>. Если значения <tex>l.next</tex> и <tex>r</tex> лежат полностью внутри отрезка <tex>[L, R]</tex>, то к самому отрезку <tex>[l.next, r]</tex> прибавляем <tex>1</tex>, а сам отрезок <tex>[L, R]</tex> разбиваем на два и по отдельности прибавляем уже отрезки <tex>[L, l.key]</tex> и <tex>[r.next.key, R]</tex>. Допустим, что на каком-то уровне у нас получилось разделить отрезок <tex>[L, R]</tex> на <tex>3</tex>. части. Но тогда на следующих уровнях мы будем уменьшать отрезок почти в два раза и только с одной стороны, поскольку другая часть отрезка уже будет иметь чёткую границу, за которую он не переходит. Итого время обработки запроса <tex>O(\log{n})</tex>.
+
Для решения данной задачи воспользуемся списком с пропусками. Когда нам приходит запрос первого типа, то мы просто добавляем числа <tex>L</tex> и <tex>R</tex> в список с пропусками (если какое-то из чисел уже было добавлено, то второй раз мы его не добавляем). После этого идём с верхнего уровня, и на каждом уровне мы ищем такие <tex>l</tex> и <tex>r</tex>, что значение <tex>l</tex> меньше <tex>L</tex>, а значение следующего за <tex>l</tex> элемента уже не меньше <tex>L</tex>. Аналогично ищем такое же <tex>r</tex>, только относительно <tex>R</tex>. Если значения <tex>l.next</tex> и <tex>r</tex> лежат полностью внутри отрезка <tex>[L, R]</tex>, то к самому отрезку <tex>[l.next, r]</tex> прибавляем <tex>1</tex>, а сам отрезок <tex>[L, R]</tex> разбиваем на три <tex>[L, l.next.key - 1]</tex>, <tex>[l.next.key, r.key]</tex> и <tex>[r.key + 1, R]</tex> и по отдельности решаем задачу уже для полученных отрезков (если для какого-то отрезка левая граница стала больше правой, то мы ничего не делаем). Допустим, что на каком-то уровне у нас получилось разделить отрезок <tex>[L, R]</tex> на <tex>3</tex> части. Но тогда на следующих уровнях мы будем уменьшать отрезок почти в два раза только с одной стороны, поскольку левая или правая часть отрезка будет равна <tex>l.next.key</tex> или <tex>r.key</tex>. Итого время обработки запроса <tex>O(\log{n})</tex>.
  
Для запросов второго типа мы снова будем спускать с верхнего уровня до нижнего. На каждом уровне найдём тот элемент, значение которого не меньше точки <tex>x</tex>. Если такой элемент нашёлся, то прибавляем к ответу значение на отрезку между найденным элементом и следующим. Потом также спускаемся на один уровень вниз, если текущий уровень не был первым. Очевидно, что данный тип запросов мы обрабатываем за <tex>O(\log{n})</tex>.
+
Для запросов второго типа мы снова будем спускать с верхнего уровня до нижнего. На каждом уровне найдём тот элемент, значение которого не меньше точки <tex>x</tex>. Если такой элемент нашёлся, то прибавляем к ответу значение на отрезку между найденным элементом и следующим. Потом также спускаемся на один уровень вниз, если текущий уровень не был первым. Поскольку уровней всего <tex>\log{n}</tex>, а на каждом уровне обойдём не более двух элементов, то данный тип запросов мы обработаем за <tex>O(\log{n})</tex>.
  
 
==См. также==
 
==См. также==
Строка 156: Строка 177:
 
*[[Поисковые структуры данных]]
 
*[[Поисковые структуры данных]]
 
*[[Skip quadtree: определение, время работы|Skip quadtree]]
 
*[[Skip quadtree: определение, время работы|Skip quadtree]]
*[http://en.wikipedia.org/wiki/Skip_graph Skip graph] — структура данных, основанная на списке с пропусками
 
  
 
==Источники информации==
 
==Источники информации==

Версия 14:22, 22 апреля 2019

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

Список с пропусками (англ. 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] (при условии, что у нас есть ссылка не текущий)
  • Легко модифицировать под различные задачи

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

Задача:
Пусть у нас есть запросы двух видов:
  1. Добавить отрезок [math][L, R][/math]
  2. Для заданной точки [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].

См. также

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