Изменения

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

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

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

Элементы односвязного списка состоят из вершин — вершины <tex>\mathtt{node}</tex>, у которых есть <tex>3</tex> поля:* <tex>\mathtt{next}</tex> <tex>-</tex> — ссылка на следующий элемент спискана данном уровне* <tex>\mathtt{key}</tex> <tex>-</tex> — ключ, который хранится в данной вершине* <tex>\mathtt{down}</tex> <tex>-</tex> — ссылка на соответственный элемент, лежащий уровнем ниже

'''struct''' node: '''node''' next, down '''K''' key Также известно, что <tex>\mathtt{head{.}key} = -\infty \ </tex> и <tex>\mathtt{tail{.}key} = \infty</tex>.,

'''list''' build_lvl ('''list''' lvl) <font color=darkgreen>// Отсеивание нечётных элементов</font> '''list''' next_lvl next_lvl.head.down = lvl.head next_lvl.tail.down = lvl.tail '''node''' i = lvl.head <font color.next.next '''node''' cur =darkgreen>// Перебор всех элементов lvl</font>next_lvl.head '''while''' (i != <tex>\neq</tex> ''null'') '''and''' (i != lvl.tail)next <tex>\neq</tex> ''null'' next_lvlcur.push_back(next = node(i.key, i, cur.next)) <font color=darkgreen>// Конструктор node(key, down, next) возвращает новую вершину с ключом key , ссылками down на нижний и ссылкой down next на соответствующую вершину предыдущего уровеняследующий элемент</font> cur = cur.next i = i.next.next <font color=darkgreen>// Переход к следующему чётному элементу</font>

'''list''' skip_list ('''list''' l): '''list''' lvl = build_lvl(l) <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 <font color=darkgreen>// Добавление следующих уровней; последний содержит не более двух элементов</font>

'''return''' lvl <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font>

 [[Файл:SkipListSearch.png|thumb|600px|Пример поиска числа <tex>8</tex>]] Алгоритм поиска элементе элемента в списке с пропусками состоит из следующих операций:

# Переместиться Переместимся на один уровень вниз и перейти к шагу <tex>2</tex>. Если мы уже на первом уровне <tex>-</tex> прекратить — прекратим поиск и вернуть вернём ссылку на текущую вершину

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

Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет <tex>\log{n}</tex> уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). Уровней всего Если же у нас будет <tex>\logk</tex> уровней, тогда на каждом уровне в среднем будет в <tex>n^{n1/k}</tex>раз элементов больше, откуда вытекает оценка времени чем уровнем выше. В таком случае время поиска элемента в <tex>-</tex> <tex>O(k \logcdot n^{n1/k})</tex>.

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

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

find(listskip.head(), key)

Для того, чтобы вставить элемент Алгоритм вставки элементов в список с пропусками, нужно запустить рекурсивную функцию, которая в каждом состоит из уровней найдёт позицию, где должен был стоять следующих шагов:# Начинаем вставку на самом верхнем уровне# Переходим к следующему элементу списка пока значение следующей ячейки меньше ключа.# Если мы на первом уровне — вставляем элемент. Иначе спускаемся ниже и возвращаемся к шагу <tex>2</tex>. Если это первый уровеньнам вернули не ''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'', а также вернуть результат броска монетки. Если же если на монете выпала «Решка».  '''node''' insert('''node''' res, то просто возвращаем такой же результат'''K''' key) '''while''' res.next <tex>\neq</tex> ''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 <tex>\neq</tex> ''null'' '''or''' res.down = ''null'' <font color=darkgreen>// Если выпал «Орёл» или мы находимся на всех уровнях первом уровне</font> res.next = node(key, down_node, res.next) '''if''' coin_flip() = ''head'' <font color=darkgreen>// Если выпал «Орёл»</font> '''return''' res. В таком случае надо создать новый верхний уровень и next '''return''' ''null'' '''return''' ''null'' Для того, чтобы вставить элемент с ключом <tex>\mathtt{key}</tex> в него текущий элементсписок с пропусками <tex>\mathtt{skip}</tex> необходимо вызвать следующую функцию  '''function''' insert_element('''list''' skip, '''K''' key) '''node''' res = insert(skip.head, key) '''if''' res <tex>\neq</tex> ''null'' '''list''' lvl lvl.head.next = node(key, res, а также вернуть ссылку на начало нового уровняlvl.tail) skip = lvl

Для того, чтобы удалить Алгоритм удаления элемента выглядит следующим образом:# Начинаем удалять элемент из списка с пропусками необходимо вызвать рекурсивную функциюверхнего уровня# Переходим к следующему элементу, которая в каждом пока значение следующего элемента меньше ключа# Если элемент существует на данном уровне, подобно поиску, найдёт позицию, где должен был стоять элемент— удаляем его с этого уровня. Во время рекурсии если это самый нижний уровеньЕсли мы не на первом уровне, то удаляем элемент из списка ещё с нижнего уровня.====Псевдокод====Функция <tex>\mathtt{delete}</tex> удаляет элемент <tex>\mathtt{key}</tex> со всех уровней.  '''function''' delete(не забывая при этом сохранить связность списка'''node''' res, '''K''' key) '''while''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.key < key res = res.next '''if''' res.down <tex>\neq</tex> ''null'' delete(res. Если это не это первый уровеньdown, то рекурсивно вызовем функцию от уровня ниже, а также удалим элемент в текущем key) '''if''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.key = key 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_{1/p} {n}</tex><tex>)</tex>.  Пусть у нас добавлено <tex>n</tex> элементов. Найдём такое распределение <tex>\left\frac{ p, q \right\}</tex>, при котором функция <tex>\dfrac{1}{px}\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> почти невозможно, поэтому на практике лучше всего использовать честную монету.

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

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

* Следующий элемент достаётся за <tex>O(1)</tex>(при условии, что у нас есть ссылка не текущий)

===Нахождение всех интерваловотрезков, покрывающих данную точку=== {{Задача|definition = Пусть у нас есть запросы двух видов:# Добавить отрезок <tex>[L, R]</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>x[l.next, r]</tex>. Найти количество интервалов, которые покрывают данную точкуСписок с пропусками позволяет решать данную задачу онлайн за прибавляем <tex>O(\log{q})1</tex> времени, где а сам отрезок <tex>q[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>1x</tex>. Когда нам приходит запрос второго типаЕсли такой элемент нашёлся, то рекурсивно прибавляем к ответу значение на отрезку между найденным элементом и следующим. Потом также спускаемся сверху на один уровень вниз и суммируем все числа, лежащие если текущий уровень не был первым. Поскольку уровней всего <tex>\log{n}</tex>, а на пути между двумя ближайшими вершинамикаждом уровне обойдём не более двух элементов, между которыми находится заданная точка. Очевидно, что оба запроса то данный тип запросов мы обрабатываем обработаем за <tex>O(\log{n})</tex>, при этом нет никакой необходимости знать запросы заранее.