Изменения

Список с пропусками состоит из нескольких уровней, на каждом из которых находится отсортированный связный список. На самом нижнем (первом) уровне располагаются все элементы. Дальше около половины элементов таким в таком же образом порядке располагаются на втором, почти четверть <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>2</tex>. Будем считать, иначе закончить операцию вставки что вставка каждого нового элементаувеличивает число уровней не более чем на один.

Таким образомЗаметим, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется <tex>\dfrac{n}{2}</tex>, на третьем уровне что вставка элемента <tex>-</tex> <tex>\dfrac{n}{4}</tex> поиск элемента и т.д. На уровне за <tex>\log{n}</tex> у нас окажется один элемент. Cоответственно вероятности попасть элементу на второй уровень — это <tex>\dfrac{O(1}{2})</tex>добавляем не более, на третий чем в <tex>\dfrac{1}{4}k</tex> и туровней элемент.д. Вероятность попасть на уровень Итого время работы <tex>O(k \log{cdot n}</tex> равна <tex>\dfrac^{1/k}{n})</tex>.

Используя монетку с распределением отличным от ====Псевдокод====Функция <tex>\left\{\dfrac{1}{2}, \ \dfrac{1}mathtt{2insert}\right\}</tex>, можно влиять возвращаем ссылку на количество элементов на верхних уровнях. Так, напримервставленный элемент в списке, при использовании монеты с распределением в котором находится <tex>\mathtt{p,q\res}</tex> (с вероятностью <tex>p</tex> выпадает «Орёл») математическое ожидание количества элементов , или ''null'', если на уровне <tex>k</tex> равно <tex>n \cdot p^k</tex>монете выпала «Решка». Таким образом, время поиска будет равно <tex>O\left( \dfrac{1}{p} \log_{\frac{1}{p}} {n} \right)</tex>.Для крайних распределений:* <tex>\{0, 1\}</tex> {{---}} <tex>O(n)</tex>* <tex>\{1, 0\}</tex> {{---}} <tex>\infty</tex>

'''node''' insert ('''node''' ires, '''K''' key, '''T''' data) '''while''' ires.key next <= key <font color=darkgreentex>// Ищем подходящее место\neq</fonttex> i = i.next() '''node''' tmp = ''null'' <font color=darkgreen>// Для записи в поле down</font> '''ifand''' ires.next.ref != ''null'' key <font color=darkgreen>// Мы не на нижнем уровне</font>key tmp res = insert (ires.ref, key) <font color=darkgreen>// Рекурсивный вызов на более низком уровне</font>next '''if''' tmp == 'node'null'' <font color=darkgreen>// Проверка броска монетки</font>down_node '''returnif''' res.down = ''null'' i.next down_node = '''new''' node (i.next, tmp, data, key) <font color=darkgreen>//Непосредственно вставка</font> null'''if''' random(0,1) > 0.5 <font color=darkgreen>// Бросок монетки</font> return i.next <font color=darkgreen>// Нужно передать новый элемент для вставки выше</font>

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> необходимо вызвать следующую функцию

'''voidfunction''' insert insert_element('''list''' skip_listskip, '''K''' key) '''node''' res = insert(skip.head, key) '''Tif''' data) res <font color=darkgreentex>// Обёрточка\neq</fonttex>''null'' '''list''' lvl insert(skip_list lvl.head.next = node(key, keyres, datalvl.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_{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>(при условии, что у нас есть ссылка не текущий)