'''Список с пропусками''' (''skip -list'') — поисковая — вероятностная структура данных, позволяющая производить операции поиска, добавления и удаления элемента в списке за достаточно малое времяоснованная на нескольких отсортированных односвязных списках.
Поиск элемента в списке производится за Отсортированный связный список является простейшей структурой с временем поиска <tex>\Theta(n)</tex>. Добавление дополнительных уровней, обеспечивающих быстрый доступ через несколько элементов, поможет улучшить асимптотику до <tex>\Theta(\log(n))</tex>; добавление и удаление элемета происходит за то же время, что и поиск, однако эти операции могут замедлить поиск в структуре.
Такая производительность достигается за счёт добавления новых уровней. При этом нижним уровнем является исходный список, а каждый следующий уровень - список, содержащий часть элементов предыдущего уровня со ссылками на эти элементы. ==ПостроениеОписание==
Список с пропусками строится на основе существующего односвязного отсортированного списка.
[[Файл:SimpleList.png]]
Добавив дополнительные уровни, каждый из которых представляет предыдущий уровень без нечетных элементов, мы получим возможность осуществлять поиск, вставку и удаление элементов подобно операциям с двоичным деревом поиска. Одинаковые элементы связаны между уровнями. Соответственно, асимптотика этих операций будет составлять <tex>\Theta(\log(n))</tex>.
[[Файл:SkipList.png]]
==Операции над структурой==
===Поиск элемента===
Допустим, что в нашем списке с пропусками существуют два уровня: <tex>kL_1</tex> уровней, при этом первым уровнем (в котором содержатся все элементы и <tex>L_1L_2</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>
Так же можно убедиться, что список Делая аналогичные подсчеты для списков с пропусками, имеющий в которых содержится больше уровней, получаем:* Для трех уровней: <tex>k3 \sqrt[3]{n}</tex> * Для четырех уровней, будет лучше всего работать с : <tex>4 \sqrt[k4]{n} </tex> элементами на уровне; время работы такого списка будет равно * Для пяти уровней: <tex>k 5 \sqrt[k5]{n} </tex>.* Для <tex>\log_2log{n}</tex> уровней же время работы составит : <tex> \log_2log{n} \times \sqrt[\log{n}]{n} = n ^ {\frac{1}{log_2log{n}}} \times \log{n} = n ^ {\log_n{2}} \times \log_2log{n} = 2\log_2log{n}</tex> Пример поиска:В списках с пропусками, в которых содержится <tex>\log{n}<code/tex> T* find (list уровней будет себя вести очень похоже на сбалансированные бинарные деревья поиска. В идеальной данной структуре соотношение между соседними уровнями будет равняться двум. Поиск в <nodetex> skip_list, K key) \log{ n}<// Возвращает собственно элемент node* pos = _find tex> списке с пропусками будет осуществляться за асимптотическое время <tex>O(skip_list, key\log{n}); return pos-</tex>key == key ? pos : NULL; // Вернёт элемент, если он есть, иначе NULL }.
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>
skip_list const float P = 0.5 int random_level(list l): list int lvl = build_lvl(lint)(log(frand()); // Здесь происходит построение первого уровняlog(1.-P)) if lvl < MAX_LEVEL return lvl return MAX_LEVEL boolean Find (int key) SkipNode x = header for i = level to 0 while x.forward[i] != NULL and x.forward[i].value < key x = x.forward[i] x = x.forward[0] return x != NULL && x.value == key void Insert(int value) SkipNode x = header SkipNode update update.assign(MAX_LEVEL + 1, 0) for i = level to 0 while (x.forward[i] != NULL and x.forward[i].value < value x = x.forward[i] update[i] = x x = x.forward[0] if x == NULL or x.value != value int lvl.size= random_level() if lvl > 2level for i = level + 1 to lvl update[i] = header level = lvl x = new SkipNode(lvl, value) for i = 0 to lvl x.forward[i] = update[i].forward[i] update[i].forward[i] = x void Erase(int value) SkipNode x = build_lvl header SkipNode update update.assign(lvlMAX_LEVEL + 1, 0) for i = level to 0 while x.forward[i] != NULL and x.forward[i].value < value x = x.forward[i] update[i] = x x = x.forward[0] if x.value == value for i = 0 to level if update[i].forward[i] != x break update[i].forward[i] = x.forward[i]; // Добавление следующих уровней; последний содержит два элемента return t; delete x while level > 0 or header.forward[level] == NULL level--
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/ Хабрахабр — Списки с пропусками]
