Изменения
Нет описания правки
'''Список с пропусками''' (англ. ''skip-list'') — вероятностная — поисковая структура данных, основанная на нескольких отсортированных односвязных спискахпозволяющая производить операции поиска, добавления и удаления элемента в списке за достаточно малое время.
Такая производительность достигается за счёт добавления новых уровней. При этом нижним уровнем является исходный список, а каждый следующий уровень - список, содержащий часть элементов предыдущего уровня со ссылками на эти элементы. ==ОписаниеПостроение==
Список с пропусками строится на основе существующего односвязного отсортированного списка.
[[Файл:SimpleList.png]]
Добавив дополнительные уровни, каждый из которых представляет предыдущий уровень без нечетных элементов, мы получим возможность осуществлять поиск, вставку и удаление элементов подобно операциям с двоичным деревом поиска. Одинаковые элементы связаны между уровнями. Соответственно, асимптотика этих операций будет составлять <tex>\Theta(\log(n))</tex>.
[[Файл:SkipList.png]]
==Операции над структурой==
===Поиск элемента===
Допустим, что в нашем списке с пропусками существуют два уровня: <tex>L_1k</tex>уровней, в котором содержатся все элементы и при этом первым уровнем (<tex>L_2L_1</tex>, в котором присутствует только часть из них. Между одинаковыми элементами этих двух списков существуют ссылки) будет исходный список.
В таком случае алгоритм поиска в этой структуре будет представлять из себя следующие операции:
# Начинаем поиск элемента в верхнем левом углу# Передвигаться будем по списку списке (<tex>L_2L_k</tex>), рассмотрим первый элемент# Переходить к следующему элементу списка, пока значение в следующей ячейке меньше или равно ключу# Переместиться в нижний на один уровень вниз и продолжить аналогичный метод перейти к пункту 2. Если рассматриваемый элемент находится на нижнем уровне - выйти из поиска по списку <tex>L_1</tex>
Пример поиска числа 8 в списке из описания:
[[Файл:SkipListSearch.png]]
Рассмотрим время работы для списка с двумя уровнями.
Тогда время работы алгоритма поиска будет зависеть от количества элементов на уровне <tex>L_2</tex>. Представим, что на этот уровень у нас случайным образом попало несколько элементов. Следовательно в худшем случае поиска мы получим следующую оценку на время работы:
<tex> \sqrt{n} + \dfrac{n}{\sqrt{n}} = 2 \sqrt{n}</tex>
===Вставка элемента===
Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется <tex>\dfrac{n}{2}</tex>, на третьем уровне <tex>\dfrac{n}{4}</tex> и т.д. На уровне <tex>\log{n}</tex> у нас окажется один элемент. Ну и соответственно вероятности попасть элементу на второй уровень — это <tex>\dfrac{1}{2}</tex>, на третий <tex>\dfrac{1}{4}</tex> и т.д. Вероятность попасть на уровень <tex>\log{n}</tex> равна <tex>\dfrac{1}{n}</tex>.
Используя монетку с распределением отличным от {<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> параллельных списков. В обоих случаях )
===Удаление элемента===
==Псевдокод==
Наглядный, но не очень эффективный по памяти вариант списка с пропусками.
В узлах списка хранятся:
* <tex>next</tex> {{---}} следующий узел
* <tex>down</tex> {{---}} тот же узел на следующем уровне
* <tex>data</tex> {{---}} данные типа T
* <tex>key</tex> {{---}} ключ типа K
Конструктор
<code>
list build_lvl (list lvl) // Отсеивание нечётных элементов
list next_lvl;
node i = lvl.head(); // Перебор всех элементов lvl
while ((i != NULL) '''and''' (i != lvl.tail()))
next_lvl.push_back(node(i.key, i)); // Добавление чётного элемента;
i = i.next.next; // он содержит ключ и ссылку на предыдущий уровень
'''return''' next_lvl;
</code>
Поиск элемента по ключу:
<code>
T find (list skip_list, K key)
node res;
'''for''' (res = skip_list.head; res.ref != NULL; res = res.ref) {
// Cпускаемся на шаг вниз, если можем (п. 3)
'''while''' (res.key <= key) // Переходим к следующему элементу (п. 2)
res = res.next();
'''return''' res.data;
</code>
Вставка:
<code>
node insert (node i, K key, T data)
'''while''' (i.key <= key) // Ищем подходящее место
i = i.next();
node tmp = '''NULL'''; // Для записи в поле down
'''if''' i.ref != '''NULL''' // Мы не на нижнем уровне
tmp = insert (i.ref, key); // Рекурсивный вызов на более низком уровне
'''if''' tmp == '''NULL''' // Проверка броска монетки
'''return''' '''NULL''';
i.next = '''new''' node (i.next, tmp, data, key); //Непосредственно вставка
'''if''' random(0,1) > 0.5 // Бросок монетки
return i.next; // Нужно передать новый элемент для вставки выше
'''else'''
return '''NULL''';
void insert (list skip_list, K key, T data) // Обёрточка
insert(skip_list.head, key, data);
</code>
Удаление:
<code>
'''void''' erase (node i, K key)
'''if''' (i == '''NULL''')
'''return''';
'''while''' (i.key <= key) // Ищем элемент
i = i.next();
erase(i.ref, key); // Удаляем с нижних уровней
'''if''' (i.key == key) // Если ключ совпадает
'''delete'''(i); // удаляем и с этого уровня
void erase (list skip_list, K key) // Обёрточка erase(skip_list.head, key);</code>==СсылкиСм. также==*[[Список]]*[[Рандомизированное бинарное дерево поиска]]*[[Поисковые структуры данных]]==Источники информации==
*[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)]
