Изменения

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

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

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

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

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

[[Файл:SkipListSearchФункция <tex>\mathtt{find}</tex> возвращает ссылку на элемент, значение которого не меньше <tex>\mathtt{key}</tex>.png]]В случае, если все элементы в списке с пропусками меньше <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>L_1</tex> и <tex>L_2</tex>. Поскольку элементы по уровням распределяются равномерно, то в среднем количество элементов между двумя соседними элементами уровня <tex>L_2</tex> будет составлять ключом <tex>\dfracmathtt{nkey}{\vert L_2 \vert}</tex>. Оценим среднее время доступа к элементу. Мы пройдём не более <tex>\vert L_2 \vert</tex> элементов на втором уровне, однако, если на каком-нибудь шаге мы спустимся на нижней уровень, то пройдём в среднем не более <tex>\dfrac{n}{\vert L_2 \vert}</tex> элементов (в противном случае мы могли бы пройти ещё один элемент на втором уровне). Минимизируем величину списке с пропусками <tex>\vert L_2 \vert + \dfracmathtt{n}{\vert L_2 \vertskip}</tex>. Очевидно, что при необходимо запустить <tex> \vert L_2 \vert = \sqrtmathtt{nfind}</tex> сумма достигает минимального значения. Таким следующим образом, время поиска элемента составляет в среднем <tex>O(\sqrt{n})</tex>, отсюда выходит, что удаление и добавления элемента также происходит за <tex>O(\sqrt{n})</tex>, а для того, чтобы эффективнее использовать такой список, нам нужно генератор равновероятных чисел с вероятностью <tex>\dfrac{1}{\sqrt{n}}</tex>.

Допустим, что у нас имеется не два, а <tex>k</tex> уровней find(skip. Тогда оптимально на каждом из <tex>k</tex> уровней проходить не более <tex>\sqrt[k]{n}</tex> элементов, отсюда выходить оценка для поискаhead, добавления и удаления элементов равная <tex>O(\sqrt[k]{n}key)</tex>.

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

Используя монетку с распределением отличным от <tex>\{\dfrac{1}{2}</tex> '''function''' insert_element('''list''' skip, <tex>\dfrac{1}{2}\}</tex>, можно влиять на количество элементов на верхних уровнях'''K''' key) '''node''' res = insert(skip. Такhead, например, при использовании монеты с распределением key) '''if''' res <tex>\{p,q\}neq</tex>}, математическое ожидание количества элементов на уровне <tex>l</tex> равно <tex dpi''null'' '''list''' lvl lvl.head.next =150>n q^l</tex>node(key, каждый уровень будет составлять <tex>q</tex> от предыдущего; время поиска будет равно <tex>O(\dfrac{k}{q} + nq^k)</tex>. Соответственно при честной монетке и <tex>\log(n)</tex> уровней получаем оценкуres, полученную ранееlvl.Для крайних распределений:* <tex>\{0, 1\}</tex> {{---}} <tex>O(k+ntail)</tex>* <tex>\{1, 0\}</tex> {{---}} <tex>\infty</tex> (если разрешить добавление новых уровней при проталкивании элемента после броска монетки; иначе <tex>O(n)</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>next</tex> \mathtt{{---}key} следующий узел* </tex>downиз списка с пропусками </tex> \mathtt{{---skip}} тот же узел на следующем уровне* </tex>data, необходимо вызвать функцию </tex> \mathtt{{---delete}} данные типа T* <tex>key\ </tex> {{---}} ключ типа Kследующим образом:

Конструктор<code> '''list''' skip_list delete('''list''' l): '''list''' lvl = build_lvl(l) <font color=darkgreen>// Здесь происходит построение первого уровня</font> '''while''' lvlskip.size() > 2 lvl = build_lvl (lvlhead, key) <font color=darkgreen>// Добавление следующих уровней; последний содержит два элемента</font> '''return''' t

'''list''' build_lvl ('''list''' lvl) ==Использование нечестной монеты==Вместо честной монеты с распределением <font color=darkgreentex>\left\{\dfrac{1}{2}, \ \dfrac{1}{2}\right\}<// Отсеивание нечётных элементовtex> можно взять в качестве случайного источника нечестную монету с распределением <tex>\{p,q\}</fonttex> '''list''' next_lvl '''node''' i = lvl.head() с вероятностью <font color=darkgreentex>// Перебор всех элементов lvlp</fonttex> '''while''' (i != ''null''выпадает «Орёл») '''and''' (i != lvl.tail()) next_lvl.push_back(node(i.key, i)) Тогда математическим ожиданием количества элементов на уровне <font color=darkgreentex>k<// Добавление чётного элемента;tex> будет <tex>n \cdot p^k</fonttex> i = i.next.next Время поиска будет равно <font color=darkgreentex>O\left( \dfrac{1}{p} \log_{1/p} {n} \right)</ он содержит ключ и ссылку tex> <tex>(</tex>на предыдущий уровень<tex>i</fonttex>-ом уровне элементов будет почти в <tex> '''return''' next_lvl \dfrac{1}{p}</codetex>Поиск элемента по ключу:раз больше, чем на <codetex> '''T''' find ('''list''' skip_list, '''K''' keyi+1) '''node''' res '''for''' (res = skip_list.head; res.ref != ''null''; res = res.ref) <font color=darkgreen/tex>// Cпускаемся -ом, значит на шаг вниз, если можем (п. 3)каждом уровне пройдём не более <tex>\dfrac{1}{p}</fonttex> '''while''' res.key <= key элементов, а уровней всего <font color=darkgreentex>\log_{1/p} {n}</ Переходим к следующему элементу (п. 2tex><tex>)</fonttex> res = res.next() '''return''' res.data Пусть у нас добавлено <tex>n</codetex>Вставка:элементов. Найдём такое распределение <codetex> '''node''' insert ('''node''' i\left\{ p, '''K''' keyq \right\}</tex>, '''T''' data) '''while''' i.key при котором функция <= key <font color=darkgreentex>\dfrac{1}{x} \log_{1// Ищем подходящее местоx} {n}</fonttex> i = iпринимает минимальное значение.next() '''node''' tmp = ''null'' Производная этой функции равна <font color=darkgreentex>-\dfrac{\ln{n} \left( \ln {(1/x)} - 1 \right)}{x^2 \ln^2{(1/ Для записи в поле downx)}}</fonttex> '''if''' i.ref != ''null'' При <font colortex>x =darkgreen>// Мы не на нижнем уровне\dfrac{1}{e}</fonttex> tmp = insert (i.refпроизводная равна нулю, key) вторая производная в точке <font colortex>x_0 =darkgreen>// Рекурсивный вызов на более низком уровне\dfrac{1}{e}</fonttex> '''if''' tmp == ''null'' больше <font color=darkgreentex>// Проверка броска монетки0</fonttex> '''return''' ''null'' i.next = '''new''' node (i.next, tmp, data, key) значит <font color=darkgreentex>x_0<//Непосредственно вставкаtex> <tex>-</fonttex> '''if''' random(0,1) > 0точка минимума.5 Значит при распределении <font color=darkgreentex>// Бросок монетки\left\{ \dfrac{1}{e}, \dfrac{e - 1}{e} \right\}</fonttex> return iвремя поиска меньше всего.next Но не стоит забывать, что это лишь теоретическая оценка и в действительности придумать источник с распределением <font color=darkgreentex>// Нужно передать новый элемент для вставки выше\left\{ \dfrac{1}{e}, \dfrac{e - 1}{e} \right\}</fonttex> '''else''' return ''null'' почти невозможно, поэтому на практике лучше всего использовать честную монету.

'''void''' insert ('''list''' skip_list, '''K''' keyДля крайних распределений:* <tex>\{0, '''T''' data) 1\}<font color=darkgreen/tex>// Обёрточка— </fonttex> insertO(skip_list.head, key, datan) </codetex>— поиск, добавление и удаления элемента, поскольку мы вместо нескольких списков используем по факту один.Удаление:* <codetex> '''void''' erase ('''node''' i\{1, '''K''' key) '''if''' i == ''null'' '''return''' '''while''' i.key <= key <font color=darkgreen>// Ищем элемент0\}</fonttex> i = i— зависит от реализации алгоритма.next() erase(i.refЕсли при каждой вставке у нас образуется не более одного уровня, key) то количество уровней будет равным <font color=darkgreentex>// Удаляем с нижних уровнейn</fonttex> '''if''' i.key == key <font color=darkgreen>// Если ключ совпадает, значит время поиска будет равным </fonttex> '''delete'''O(in) <font color=darkgreen>// удаляем и с этого уровня</fonttex>.

 Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ:* Базы данныхБыстрая вставка элемента, поскольку не требуется каким-либо образом изменять другие элементы (только предыдущий элемент)* Распределённые вычисления и p2pПроще реализовать, чем сбалансированные деревья или хеш-таблицы* Следующий элемент достаётся за <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>[l.next, r]</tex> прибавляем <tex>1</tex>, а сам отрезок <tex>[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>x</tex>. Если такой элемент нашёлся, то прибавляем к ответу значение на отрезку между найденным элементом и следующим. Потом также спускаемся на один уровень вниз, если текущий уровень не был первым. Поскольку уровней всего <tex>\log{n}</tex>, а на основе списка с пропускамикаждом уровне обойдём не более двух элементов, то данный тип запросов мы обработаем за <tex>O(\log{n})</tex>. 

Структуры на основе списка с пропусками:*[[Skip quadtree: определение, время работы|Skip quadtree]]*[http://en.wikipedia.org/wiki/Skip_graph Википедия — Skip graph(En)]

*[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]