Изменения
Нет описания правки
'''Список с пропусками''' (англ. ''skip list'') — поисковая структура данных, позволяющая реализующая интерфейс упорядоченного множества, позволяет производить операции поиска, добавления и удаления элемента в списке за достаточно малое время.
Поиск элемента в списке производится за <tex>\Theta(\log(n))</tex>; добавление и удаление элемета происходит за то же время, что и поиск, однако эти операции могут замедлить поиск в структуре.
# Переместиться на один уровень вниз и перейти к пункту 2. Если рассматриваемый элемент находится на нижнем уровне - выйти из поиска
Пример поиска числа <tex>8 </tex> в списке из описания:
[[Файл:SkipListSearch.png]]
Используя монетку с распределением отличным от <tex>\{\dfrac{1}{2}</tex>, <tex>\dfrac{1}{2}\}</tex>, можно влиять на количество элементов на верхних уровнях. Так, например, при использовании монеты с распределением <tex>\{p,q\}</tex>}, математическое ожидание количества элементов на уровне <tex>l</tex> равно <tex dpi=150>n q^l</tex>, каждый уровень будет составлять <tex>q</tex> от предыдущего; время поиска будет равно <tex>O(\dfrac{k}{q} + nq^k)</tex>. Соответственно при честной монетке и <tex>\log(n)</tex> уровней получаем оценку, полученную ранее.
Для крайних распределений:
* {<tex>\{0, 1\}</tex>{{---}} - <tex>O(k+n)</tex>* {<tex>\{1, 0\}</tex>{{---}} - <tex>\infty</tex> (если разрешить добавление новых уровней при проталкивании элемента после броска монетки; иначе <tex>O(n)</tex>)
===Удаление элемента===
Конструктор
<code>
'''list''' skip_list ('''list ''' l): '''list ''' lvl = build_lvl(l); <font color=darkgreen>// Здесь происходит построение первого уровня</font> '''while''' (lvl.size() > 2) lvl = build_lvl (lvl); <font color=darkgreen>// Добавление следующих уровней; последний содержит два элемента</font> '''return''' t;
'''list ''' build_lvl ('''list ''' lvl) <font color=darkgreen>// Отсеивание нечётных элементов</font> '''list ''' next_lvl; '''node ''' i = lvl.head(); <font color=darkgreen>// Перебор всех элементов lvl</font> '''while (''' (i != NULL''null'') '''and''' (i != lvl.tail())) next_lvl.push_back(node(i.key, i)); <font color=darkgreen>// Добавление чётного элемента;</font> i = i.next.next; <font color=darkgreen>// он содержит ключ и ссылку на предыдущий уровень</font> '''return''' next_lvl;
</code>
Поиск элемента по ключу:
<code>
'''T ''' find ('''list ''' skip_list, '''K ''' key) '''node ''' res; '''for''' (res = skip_list.head; res.ref != '''NULL'null''; res = res.ref) <font color=darkgreen>// Cпускаемся на шаг вниз, если можем (п. 3)</font> '''while''' (res.key <= key) <font color=darkgreen>// Переходим к следующему элементу (п. 2)</font> res = res.next(); '''return''' res.data;
</code>
Вставка:
<code>
'''node ''' insert ('''node ''' i, '''K ''' key, '''T ''' data) '''while''' (i.key <= key) <font color=darkgreen>// Ищем подходящее место</font> i = i.next(); '''node ''' tmp = ''null'NULL'''; <font color=darkgreen>// Для записи в поле down</font> '''if''' i.ref != '''NULL'null'' <font color=darkgreen>// Мы не на нижнем уровне</font> tmp = insert (i.ref, key); <font color=darkgreen>// Рекурсивный вызов на более низком уровне</font> '''if''' tmp == '''NULL'null'' <font color=darkgreen>// Проверка броска монетки</font> '''return''' '''NULL'null''; i.next = '''new''' node (i.next, tmp, data, key); <font color=darkgreen>//Непосредственно вставка</font> '''if''' random(0,1) > 0.5 <font color=darkgreen>// Бросок монетки</font> return i.next; <font color=darkgreen>// Нужно передать новый элемент для вставки выше</font>
'''else'''
return ''null'NULL''';
'''void''' insert ('''list ''' skip_list, '''K ''' key, '''T ''' data) <font color=darkgreen>// Обёрточка</font> insert(skip_list.head, key, data);
</code>
Удаление:
<code>
'''void''' erase ('''node ''' i, '''K ''' key) '''if''' (i == '''NULL'null'') '''return'''; '''while''' (i.key <= key) <font color=darkgreen>// Ищем элемент</font> i = i.next(); erase(i.ref, key); <font color=darkgreen>// Удаляем с нижних уровней</font> '''if''' (i.key == key) <font color=darkgreen>// Если ключ совпадает</font> '''delete'''(i); <font color=darkgreen>// удаляем и с этого уровня</font>
'''void''' erase ('''list ''' skip_list, '''K ''' key) <font color=darkgreen>// Обёрточка</font> erase(skip_list.head, key);
</code>
==Применение==* Базы данных* Распределённые вычисления и p2p* Масштабируемые параллельные приоритетные очереди и словариВ вычислительной геометрии широко применяются структуры на основе списка с пропусками.
==См. также==
*[[Список]]
*[[Рандомизированное бинарное дерево поиска]]
*[[Поисковые структуры данных]]
Структуры на основе списка с пропусками:
*[[Skip quadtree: определение, время работы]]
*[http://en.wikipedia.org/wiki/Skip_graph - Википедия — Skip graph(En)]
==Источники информации==
*[http://habrahabr.ru/post/111913/ Хабрахабр — Списки с пропусками]
