Изменения

Список с пропусками состоит из нескольких уровней, на каждом из которых находится отсортированный связный список. На самом нижнем (первом) уровне располагаются все элементы. Дальше около половины элементов таким в таком же образом порядке располагаются на втором, почти четверть <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>\mathtt{key}</tex> — ключ, который хранится в данной вершине* <tex>\mathtt{down}</tex> — ссылка на соответственный элемент, лежащий уровнем ниже

Элементы односвязного списка состоят из вершин <tex> '''struct''' node</tex>, у которых есть <tex>3</tex> поля:* <tex> '''node''' next</tex> <tex>-</tex> ссылка на следующий элемент списка, down* <tex> '''K''' key</tex> <tex>-</tex> ключ, который хранится в данной вершине* <tex>down</tex> <tex>-</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> '''whilenode''' i = l.head '''node''' j = lvl.size() > 2 head '''while''' j <font color=darkgreentex>// Добавление следующих уровней; последний содержит не более двух элементов\neq</fonttex> 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 <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font>

 [[Файл:SkipListSearch.png|thumb|600px|Пример Алгоритм поиска числа <tex>8</tex>]] Допустим, что элемента в нашем списке с пропусками существуют <tex>k</tex> уровней, при этом первым уровнем будет исходный список. В таком случае алгоритм поиска в этой структуре будет представлять состоит из себя следующие операцииследующих операций: # Начинаем поиск элемента в самом верхнем (<tex>k</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>\dfrac{n}{2}neq</tex>, на третьем уровне ''null'' '''and''' res.next.key <tex>-</tex> <tex>\dfrac{n}{4}</tex> и т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>\log{n}neq</tex> у нас окажется один элемент''null'' '''or''' res. Cоответственно вероятности попасть элементу на второй уровень — это down = ''null'' <texfont color=darkgreen>\dfrac{1}{2}</tex>, / Если выпал «Орёл» или мы находимся на третий <tex>\dfrac{1}{4}первом уровне</texfont> и т res.дnext = node(key, down_node, res. Вероятность попасть на уровень next) '''if''' coin_flip() = ''head'' <texfont color=darkgreen>\log{n}</tex> равна <tex>\dfrac{1}{n}/ Если выпал «Орёл»</texfont> '''return''' res.next '''return''' ''null'' '''return''' ''null''

Используя монетку Для того, чтобы вставить элемент с распределением отличным от ключом <tex>\left\{\dfrac{1}{2}, \ \dfrac{1}mathtt{2}\right\key}</tex>, можно влиять на количество элементов на верхних уровнях. Так, например, при использовании монеты в список с распределением пропусками <tex>\mathtt{p,q\skip}</tex> необходимо вызвать следующую функцию  '''function''' insert_element(с вероятностью <tex>p</tex> выпадает «Орёл»'''list''' skip, '''K''' key) математическое ожидание количества элементов на уровне <tex>k</tex> равно <tex>n \cdot p^k</tex> '''node''' res = insert(skip. Таким образомhead, время поиска будет равно key) '''if''' res <tex>O\left( \dfrac{1}{p} \log_{\frac{1}{p}} {n} \right)neq</tex>.''null''Для крайних распределений: '''list''' lvl* <tex>\{0 lvl.head.next = node(key, res, 1\}</tex> {{---}} <tex>O(nlvl.tail)</tex>* <tex>\{1, 0\}</tex> {{---}} <tex>\infty</tex> 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_{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> почти невозможно, поэтому на практике лучше всего использовать честную монету. Для крайних распределений:* <tex>\{0, тогда необходимо удалить эти уровни 1\}</tex> — <tex>O(кроме первогоn)</tex> — поиск, добавление и удаления элемента, поскольку мы вместо нескольких списков используем по факту один.* <tex>\{1, 0\}</tex> — зависит от реализации алгоритма. Если при каждой вставке у нас образуется не забыть вернуть ссылку на начало самого верхнего более одного уровня, то количество уровней будет равным <tex>n</tex>, значит время поиска будет равным <tex>O(n)</tex>.

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

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