Изменения

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

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

[[Файл '''struct''' node:SkipList.png]] '''node''' next, down '''K''' key

'''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>

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

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

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

[[Файл:SkipListSearch find(skip.png]]head, key)

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

Функция Заметим, что вставка элемента <tex>-</tex> поиск элемента и за <tex>\mathtt{find}O(1)</tex> возвращает ссылку на элементдобавляем не более, значение которого не меньше чем в <tex>\mathtt{key}k</tex>уровней элемент. В случае, если все элементы в списке с пропусками меньше Итого время работы <tex>O(k \mathttcdot n^{key1/k})</tex>, то возвращается ссылка на конец списка с пропусками. '''T''' find ('''list''' skip_list, '''K''' key) '''node''' res '''for''' (res = skip_list.head; res.ref != ''null''; res = res.ref) <font color=darkgreen>// Пока ещё не дошли до первого уровня </font>Псевдокод==== '''while''' res.key Функция < key <font color=darkgreentex>// Пока значение вершины меньше ключа\mathtt{insert} \ </fonttex> res = res.next() возвращаем ссылку на вставленный элемент в списке, в котором находится <font color=darkgreentex>// Перейти к следующей вершине в текущем уровне\mathtt{res}</fonttex> , или ''null'return''' res, если на монете выпала «Решка».

'''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>2\mathtt{skip}</tex># Иначе закончить операцию вставкинеобходимо вызвать следующую функцию

Таким образом '''function''' insert_element('''list''' skip, если использовать честную монету'''K''' key) '''node''' res = insert(skip.head, то математическое ожидание количества элементов на втором уровне равняется key) '''if''' res <tex>\dfrac{n}{2}</tex>, на третьем уровне <tex>-neq</tex> <tex>\dfrac{n}{4}</tex> и т''null'' '''list''' lvl lvl.дhead. На уровне <tex>\log{n}</tex> у нас окажется один элемент. Ну и соответственно вероятности попасть элементу на второй уровень — это <tex>\dfrac{1}{2}</tex>next = node(key, res, на третий <tex>\dfrac{1}{4}</tex> и т.д. Вероятность попасть на уровень <tex>\log{n}</tex> равна <tex>\dfrac{1}{n}</tex>lvl.tail) skip = lvl

Используя монетку ===Удаление элемента===Алгоритм удаления элемента выглядит следующим образом:# Начинаем удалять элемент с распределением отличным от <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{k}{q} + nq^k\right)</tex>. Соответственно при честной монетке и <tex>\log(n)</tex> уровней получаем оценку, полученную ранеето удаляем элемент ещё с нижнего уровня.Для крайних распределений:====Псевдокод====* Функция <tex>\mathtt{0, 1\}</tex> {{---}delete} <tex>O(k+n)</tex>* удаляет элемент <tex>\mathtt{1, 0\key}</tex> {{---}} <tex>\infty</tex> (если разрешить добавление новых со всех уровней при проталкивании элемента после броска монетки; иначе <tex>O(n)</tex>).

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

'''void''' insert Аналогично со вставкой удаление <tex>-</tex> поиск элемента за <tex>O('''list''' skip_list, '''K''' key, '''T''' datak \cdot n^{1/k}) <font color=darkgreen/tex> плюс удаление на каждом уровне за <tex>O(1)</tex>. Итого <tex>-</ Обёрточкаtex> <tex>O(k \cdot n^{1/k})</fonttex> insert(skip_list.head, key, data)

===Удаление элемента===Алгоритм удаления достаточно тривиален. # Найти удаляемый Для того, чтобы удалить элемент# Удалить его со всех уровней<tex>\mathtt{key}</tex> из списка с пропусками <tex>\mathtt{skip}</tex>, необходимо вызвать функцию <tex>\mathtt{delete} \ </tex> следующим образом:

Функция <tex>\mathtt{erase}</tex> удаляет вершину <tex>i</tex> из списка с пропусками delete(skip.head, key)

'''void''' erase ('''node''' i, '''K''' key) '''if''' i == ''null''Использование нечестной монеты== '''return''' '''while''' i.key Вместо честной монеты с распределением <tex>\left\{\dfrac{1}{2}, \ \dfrac{1}{2}\right\}<= key /tex> можно взять в качестве случайного источника нечестную монету с распределением <font color=darkgreentex>\{p,q\}<// Ищем элементtex> (с вероятностью <tex>p</fonttex> i = i.next(выпадает «Орёл») erase(i.ref, key) Тогда математическим ожиданием количества элементов на уровне <font color=darkgreentex>k</tex> будет <tex>n \cdot p^k</ Удаляем с нижних уровнейtex>. Время поиска будет равно <tex>O\left( \dfrac{1}{p} \log_{1/p} {n} \right)</fonttex> '''if''' i.key == key <font color=darkgreentex>(</tex>на <tex>i</ Если ключ совпадаетtex>-ом уровне элементов будет почти в <tex>\dfrac{1}{p}</fonttex> раз больше, чем на <tex> '''delete'''(i+1) <font color=darkgreen/tex>-ом, значит на каждом уровне пройдём не более <tex>\dfrac{1}{p}</tex> элементов, а уровней всего <tex>\log_{1/p} {n}</ удаляем и с этого уровняtex><tex>)</fonttex>.

Для тогоПусть у нас добавлено <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>key-</tex> из списка с пропусками точка минимума. Значит при распределении <tex>list\left\{ \dfrac{1}{e}, \dfrac{e - 1}{e} \right\}</tex> достаточно вызвать функцию время поиска меньше всего. Но не стоит забывать, что это лишь теоретическая оценка и в действительности придумать источник с распределением <tex>\mathttleft\{erase\dfrac{1}{e}, \dfrac{e - 1}{e} \right\}</tex> следующим образом:почти невозможно, поэтому на практике лучше всего использовать честную монету.

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

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

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