Изменения
Нет описания правки
'''Список с пропусками''' (''skip-list'') — вероятностная — поисковая структура данных, основанная на нескольких отсортированных односвязных спискахпозволяющая производить операции поиска, добавления и удаления элемента в списке за достаточно малое время.
Такая производительность достигается за счёт добавления новых уровней. При этом нижним уровнем является исходный список, а каждый следующий уровень - список, содержащий часть элементов предыдущего уровня со ссылками на эти элементы. ==ОписаниеПостроение==
Список с пропусками строится на основе существующего односвязного отсортированного списка.
[[Файл:SimpleList.png]]
Добавив дополнительные уровни, каждый из которых представляет предыдущий уровень без нечетных элементов, мы получим возможность осуществлять поиск, вставку и удаление элементов подобно операциям с двоичным деревом поиска. Одинаковые элементы связаны между уровнями. Соответственно, асимптотика этих операций будет составлять <tex>\Theta(\log(n))</tex>.
[[Файл:SkipList.png]]
==Операции над структурой==
===Поиск элемента===
Допустим, что в нашем списке с пропусками существуют два уровня: <tex>L_1k</tex>уровней, в котором содержатся все элементы и при этом первым уровнем (<tex>L_2L_1</tex>, в котором присутствует только часть из них. Между одинаковыми элементами этих двух списков существуют ссылки) будет исходный список.
В таком случае алгоритм поиска в этой структуре будет представлять из себя следующие операции:
# Начинаем поиск элемента в верхнем левом углу# Передвигаться будем по списку списке (<tex>L_2</tex>L_k), рассмотрим первый элемент# Переходить к следующему элементу списка, пока значение в следующей ячейке меньше или равно ключу# Переместиться в нижний на один уровень вниз и продолжить аналогичный метод перейти к пункту 2. Если рассматриваемый элемент находится на нижнем уровне - выйти из поиска по списку <tex>L_1</tex>
Пример поиска числа 8 в списке из описания:
[[Файл:SkipListSearch.png]]
Рассмотрим время работы для списка с двумя уровнями.
Тогда время работы алгоритма поиска будет зависеть от количества элементов на уровне <tex>L_2</tex>. Представим, что на этот уровень у нас случайным образом попало несколько элементов. Следовательно в худшем случае поиска мы получим следующую оценку на время работы:
<tex> \sqrt{n} + \dfrac{n}{\sqrt{n}} = 2 \sqrt{n}</tex>
node* _find (list <node> skip_list, K key) { // Возвращает место элемента
node * res;
for (res = skip_list.begin(); res->ref != NULL; res = res->ref) {
while (res->key <= key) // Переходим к следующему элементу (п. 2)
res = res->next();
} // Спускаемся на шаг вниз, если можем (п. 3)
return res; // Возвращаем позицию элемента, либо (в случае отсутствия)
} // позицию, после которой его следует вставить
</code>
===Вставка элемента===
Для вставки элемента в список с пропусками, нам необходимо выполнить следующие шаги:
Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется <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</tex>, <tex>q</tex>}, математическое ожидание количества элементов на количество уровнейуровне <tex>l</tex> равно <tex>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) && (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/ Хабрахабр — Списки с пропусками]
