Изменения

'''Список [[Файл:Skip list example.png|thumb|550px|Пример списка с пропусками''' (''skip list'') — поисковая структура данных, позволяющая производить операции поиска, добавления и удаления элемента в списке за достаточно малое время.]]

Поиск элемента '''Список с пропусками''' (англ. ''skip list'') — вероятностная структура данных, позволяющая в списке производится среднем за <tex>\ThetaO(\log(n))</tex>; добавление и удаление элемета происходит за то же времявремени выполнять операции добавления, что удаления и поиск, однако эти операции могут замедлить поиск в структурепоиска элементов.

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

Список с пропусками строится на основе существующего односвязного отсортированного списка[[Файл:SimpleList.png|thumb|600px|Односвязный отсортированный список]]

[[Файл:SimpleListSkipList.png|thumb|600px|Получившийся список с пропусками]]Допустим, что нам задан односвязный отсортированный список и мы хотим построить на его основе список с пропусками, позволяющий в среднем за <tex>O(\log{n})</tex> времени выполнять операции добавления, удаления и поиска элементов.

Добавив дополнительные уровниНа самом нижнем уровне списка с пропусками мы расположим исходный список. На втором уровне — всё элементы с чётными номерами, причём каждый из которых представляет предыдущий элемент будет ссылаться на соответствующий ему элемент на нижнем уровне. Таким же образом построим и третий уровень без нечетных элементов, мы получим возможность осуществлять поисккуда будем добавлять только те элементы, вставку номера которых кратны четырём. Аналогичным образом построим и удаление элементов подобно операциям с двоичным деревом поиска. Соответственно, асимптотика этих операций будет составлять <tex>\Theta(\log(n))</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> — ссылка на соответственный элемент, лежащий уровнем ниже  '''struct''' node: '''node''' next, down '''K''' key Также известно, что <tex>\mathtt{head{.}key} = -\infty \ </tex> и <tex>\mathtt{tail{.}key} = \infty</tex>,  Функция <tex>\ \mathtt{build\_lvl} \ </tex> возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.  '''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 <tex>\neq</tex> ''null'' '''and''' i.next <tex>\neq</tex> ''null'' cur.next = node(key, i, cur.next) <font color=darkgreen>// Конструктор node(key, down, next) возвращает новую вершину с ключом key, ссылками down на нижний и next на следующий элемент</font> cur = cur.next i = i.next.next <font color=darkgreen>// Переход к следующему чётному элементу</font> '''return''' next_lvl  Функция <tex>\ \mathtt{skip\_list} \ </tex> принимает в качестве аргумента односвязный отсортированный список и возвращает новый список с пропусками, построенный на его основе.  '''list''' skip_list('''list''' l):SkipList '''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.png]]size > 2 lvl = build_lvl(lvl) '''return''' lvl <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font>

Допустим, что Алгоритм поиска элемента в нашем списке с пропусками существуют состоит из следующих операций:# Начинаем поиск элемента в самом верхнем уровне# Переходим к следующему элементу списка, пока значение в следующей ячейке меньше# Переместимся на один уровень вниз и перейти к шагу <tex>2</tex>. Если мы уже на первом уровне — прекратим поиск и вернём ссылку на текущую вершину В конце алгоритма функция вернёт элемент, значение которого не меньше ключа <tex>\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>\mathtt{find}</tex> возвращает ссылку на элемент, значение которого не меньше <tex>L_1\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> Для того, чтобы найти элемент с ключом <tex>\mathtt{key}</tex> в списке с пропусками <tex>\mathtt{skip}</tex> необходимо запустить <tex>\mathtt{find}</tex> следующим образом  find(skip.head, key)

В таком случае алгоритм поиска ===Вставка элемента===Алгоритм вставки элементов в этой структуре будет представлять список с пропусками состоит из себя следующие операцииследующих шагов:# Начинаем поиск элемента в вставку на самом верхнем списке (<tex>L_k), рассмотрим первый элементуровне# Переходить Переходим к следующему элементу списка, пока значение в следующей ячейке ячейки меньше или равно ключуключа.# Переместиться Если мы на один уровень вниз первом уровне — вставляем элемент. Иначе спускаемся ниже и перейти возвращаемся к пункту шагу <tex>2</tex>. Если рассматриваемый нам вернули не ''null'' — вставляем элемент находится на нижнем текущем уровне - выйти из поискатоже.# Кидаем монетку и если выпал «Орёл», то возвращаем ссылку на текущий элемент, иначе — ''null''. Если мы были не на первом уровне и нам вернули ''null'' — возвращаем его без броска монетки.

Пример поиска числа 8 Отдельно стоит обработать случай, когда вставка нового элемента увеличивает число уровней. Тогда необходимо создать ещё один отсортированный список, в списке из описания:котором будет всего один текущий элемент, и не забыть присвоить списку с пропусками новую ссылку на верхний уровень. Будем считать, что вставка каждого нового элемента увеличивает число уровней не более чем на один.

[[Файл:SkipListSearchЗаметим, что вставка элемента <tex>-</tex> поиск элемента и за <tex>O(1)</tex> добавляем не более, чем в <tex>k</tex> уровней элемент. Итого время работы <tex>O(k \cdot n^{1/k})</tex>.png]]

Рассмотрим время работы для списка с двумя уровнями.====Псевдокод====Тогда время работы алгоритма поиска будет зависеть от количества элементов Функция <tex>\mathtt{insert} \ </tex> возвращаем ссылку на уровне вставленный элемент в списке, в котором находится <tex>L_2\mathtt{res}</tex>. Представим, что или ''null'', если на этот уровень у нас случайным образом попало несколько элементовмонете выпала «Решка». Следовательно в худшем случае поиска мы получим следующую оценку на время работы:

'''node''' insert('''node''' res, '''K''' key) '''while''' res.next <tex> \approx \vert L_2\vert + \dfrac{\vert L_1\vert }{\vert L_2\vert } 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>\vert L_2\vert + \dfrac{n}{\vert L_2\vert }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>\vert L_2 mathtt{key}</tex> в список с пропусками <tex>\vert ^ 2 = nmathtt{skip}</tex>необходимо вызвать следующую функцию

===Удаление элемента===Алгоритм удаления элемента выглядит следующим образом:# Начинаем удалять элемент с верхнего уровня# Переходим к следующему элементу, пока значение следующего элемента меньше ключа# Если элемент существует на данном уровне — удаляем его с этого уровня. Если мы не на первом уровне, то удаляем элемент ещё с нижнего уровня.====Псевдокод====Функция <tex> \sqrtmathtt{ndelete} + \dfrac{n}{\sqrt{n}} = 2 </tex> удаляет элемент <tex>\sqrtmathtt{nkey}</tex>со всех уровней.

Так же можно убедиться '''function''' delete('''node''' res, что список с пропусками, имеющий <tex>k<tex> уровней, будет лучше всего работать с '''K''' key) '''while''' res.next <tex>\sqrt[k]{n} neq</tex> элементами на уровне; время работы такого списка будет равно ''null'' '''and''' res.next.key < key res = res.next '''if''' res.down <tex>k \sqrt[k]{n} neq</tex>''null'' delete(res.down, key)Для '''if''' res.next <tex>\log_2{n}neq</tex> уровней же время работы составит <tex> \log_2{n} \times \sqrt[\log{n}]{n} ''null'' '''and''' res.next.key = n ^ {\frac{1}{log_2{n}}} \times \log{n} key res.next = n ^ {\log_n{2}} \times \log_2{n} = 2\log_2{n}</tex>res.next.next

Пример поиска:Аналогично со вставкой удаление <codetex> T* find (list -</tex> поиск элемента за <nodetex> skip_list, K key) O(k \cdot n^{ 1/k})</ Возвращает собственно элемент node* pos = _find tex> плюс удаление на каждом уровне за <tex>O(skip_list, key1); return pos</tex>. Итого <tex>-</tex> <tex>key == key ? pos : NULL; O(k \cdot n^{1/k})</ Вернёт элемент, если он есть, иначе NULL }tex>.

node* _find (list Для того, чтобы удалить элемент <nodetex> skip_list, K \mathtt{key) }</tex> из списка с пропусками <tex>\mathtt{ skip}</tex>, необходимо вызвать функцию <tex>\mathtt{delete} \ </ Возвращает место элементаtex> следующим образом: node * res; for delete(res = skip_listskip.begin(head, key); res->ref ! ==Использование нечестной монеты= NULL; res = res-Вместо честной монеты с распределением <tex>\left\{\dfrac{1}{2}, \ \dfrac{1}{2}\right\}</tex> можно взять в качестве случайного источника нечестную монету с распределением <tex>ref) \{ while p,q\}</tex> (res-с вероятностью <tex>key p<= key/tex> выпадает «Орёл») . Тогда математическим ожиданием количества элементов на уровне <tex>k</tex> будет <tex>n \cdot p^k</ Переходим к следующему элементу (пtex>. 2) res = res-Время поиска будет равно <tex>nextO\left(); \dfrac{1}{p} \log_{1/p} {n} \right)</ Спускаемся на шаг вниз, если можем tex> <tex>(п. 3) return res; </tex>на <tex>i</ Возвращаем позицию элемента, либо (tex>-ом уровне элементов будет почти в случае отсутствия) <tex>\dfrac{1}{p} <// позициюtex> раз больше, после которой его следует вставитьчем на <tex>(i+1)</codetex>===Вставка элемента===Для вставки элемента в список с пропусками-ом, нам необходимо выполнить следующие шаги:# Найти с помощью алгоритма поиска позицию, куда нам надо вставить этот элемент# Вставить наш элемент в нижний уровень списка с пропусками# «Подбросить монетку» и в зависимости от результата протолкнуть элемент значит на уровень выше# Повторять предыдущий шаг до тех поркаждом уровне пройдём не более <tex>\dfrac{1}{p}</tex> элементов, пока у нас «подброс монетки» дает положительный результата уровней всего <tex>\log_{1/p} {n}</tex><tex>)</tex>.

Таким образом, если использовать честную монету, то математическое ожидание количества Пусть у нас добавлено <tex>n</tex> элементов на втором уровне равняется . Найдём такое распределение <tex>\dfracleft\{n}{2p, q \right\}</tex>, на третьем уровне при котором функция <tex>\dfrac{n1}{x} \log_{1/x}{4n}</tex> и тпринимает минимальное значение.д. На уровне Производная этой функции равна <tex>-\logdfrac{\ln{n} \left( \ln {(1/x)} - 1 \right)}{x^2 \ln^2{(1/x)}}</tex> у нас окажется один элемент. Ну и соответственно вероятности попасть элементу на второй уровень — это При <tex>x = \dfrac{1}{2e}</tex>производная равна нулю, на третий вторая производная в точке <tex>x_0 = \dfrac{1}{4e}</tex> и тбольше <tex>0</tex>, значит <tex>x_0</tex> <tex>-</tex> точка минимума.д. Вероятность попасть на уровень Значит при распределении <tex>\logleft\{n\dfrac{1}{e}, \dfrac{e - 1}{e} \right\}</tex> равна время поиска меньше всего. Но не стоит забывать, что это лишь теоретическая оценка и в действительности придумать источник с распределением <tex>\left\{ \dfrac{1}{ne}, \dfrac{e - 1}{e} \right\}</tex>почти невозможно, поэтому на практике лучше всего использовать честную монету.

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

==Применение=Удаление элемента===Алгоритм удаления достаточно тривиален. # Найти удаляемый элемент# Удалить его со всех уровней

==Псевдокод==Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ:Наглядный* Быстрая вставка элемента, но поскольку не очень эффективный по памяти вариант списка с пропусками.требуется каким-либо образом изменять другие элементы (только предыдущий элемент)* Проще реализовать, чем сбалансированные деревья или хеш-таблицы* Следующий элемент достаётся за <tex>O(1)</tex> (при условии, что у нас есть ссылка не текущий)* Легко модифицировать под различные задачи

Конструктор{{Задача|definition = Пусть у нас есть запросы двух видов:# Добавить отрезок <tex>[L, R]<code/tex>skip_list (list l): list lvl = build_lvl(l); # Для заданной точки <tex>x<// Здесь происходит построение первого уровняtex> вычислить количество отрезков, которые её покрывают. while (lvlНеобходимо для каждого запроса второго типа вывести ответ.size() > 2) lvl = build_lvl (lvl); // Добавление следующих уровней; последний содержит два элемента return t;}}

list build_lvl (list lvl) Для решения данной задачи воспользуемся списком с пропусками. Когда нам приходит запрос первого типа, то мы просто добавляем числа <tex>L</tex> и <tex>R</ Отсеивание нечётных элементов list next_lvl; node i = lvl.headtex> в список с пропусками (если какое-то из чисел уже было добавлено, то второй раз мы его не добавляем); . После этого идём с верхнего уровня, и на каждом уровне мы ищем такие <tex>l</tex> и <tex>r</ Перебор всех элементов lvl while ((i != NULL) && (i != lvl.tail())) next_lvl.push_back(node(i.keytex>, i)); что значение <tex>l</tex> меньше <tex>L</ Добавление чётного tex>, а значение следующего за <tex>l</tex> элемента; i = iуже не меньше <tex>L</tex>.nextАналогично ищем такое же <tex>r</tex>, только относительно <tex>R</tex>. Если значения <tex>l.next; <// он содержит ключ tex> и ссылку на предыдущий уровень return next_lvl;<tex>r</codetex>Поиск элемента по ключу:лежат полностью внутри отрезка <tex>[L, R]<code/tex>T find (list skip_list, K key) node res; for (res = skip_listто к самому отрезку <tex>[l.head; res.ref != NULL; res = res.ref) { next, r]</tex> прибавляем <tex>1</tex>, а сам отрезок <tex>[L, R]</ Cпускаемся tex> разбиваем на шаг внизтри <tex>[L, если можем (пl. 3) while (resnext.key - 1]<= key) // Переходим к следующему элементу (пtex>, <tex>[l. 2) res = resnext.next(); return reskey, r.data;key]</codetex>Вставка:и <codetex>node insert (node i, K [r.key+ 1, T data) while (i.key R]<= key) // Ищем подходящее место i = i.nexttex> и по отдельности решаем задачу уже для полученных отрезков (если для какого-то отрезка левая граница стала больше правой, то мы ничего не делаем); node tmp = NULL; // Для записи в поле down if i.ref != NULL // Мы не Допустим, что на нижнем каком-то уровне tmp = insert (i.refу нас получилось разделить отрезок <tex>[L, key); R]</tex> на <tex>3</ Рекурсивный вызов tex> части. Но тогда на более низком уровне if tmp == NULL // Проверка броска монетки return NULL; iследующих уровнях мы будем уменьшать отрезок почти в два раза только с одной стороны, поскольку левая или правая часть отрезка будет равна <tex>l.next = new node (i.next, tmp, data, key); </tex> или <tex>r.key</Непосредственно вставка if randomtex>. Итого время обработки запроса <tex>O(0,1\log{n}) </tex> 0.5 // Бросок монетки return i.next; // Нужно передать новый элемент для вставки выше else return NULL;

void insert (list skip_listДля запросов второго типа мы снова будем спускать с верхнего уровня до нижнего. На каждом уровне найдём тот элемент, K key, T data) значение которого не меньше точки <tex>x<// Обёрточка insert(skip_listtex>.headЕсли такой элемент нашёлся, keyто прибавляем к ответу значение на отрезку между найденным элементом и следующим. Потом также спускаемся на один уровень вниз, data);если текущий уровень не был первым. Поскольку уровней всего <tex>\log{n}</codetex>Удаление:, а на каждом уровне обойдём не более двух элементов, то данный тип запросов мы обработаем за <codetex>void erase O(node i, K key\log{n}) if (i == NULL) return; while (i.key <= key) // Ищем элемент i = i.next(); erase(i.ref, key); // Удаляем с нижних уровней if (itex>.key == key) // Если ключ совпадает delete(i); // удаляем и с этого уровня

*[[Поисковые структурыданных]]*[[Skip quadtree: определение, время работы|Skip quadtree]] ==СсылкиИсточники информации==*[http://habrahabr.ru/post/111913/ Хабрахабр — Списки с пропусками]*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D1%81_%D0%BF%D1%80%D0%BE%D0%BF%D1%83%D1%81%D0%BA%D0%B0%D0%BC%D0%B8 Википедия — списоки списки с пропусками(Ru)]*[http://en.wikipedia.org/wiki/Skip_list Википедия Wikipedia — списки с пропусками(En)]*[http://bit.ly/LiNe8M Курс kiev-clrs — Списки с пропускамиskip list]