390
правок
Изменения
→Вставка элемента
Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется <tex>\dfrac{n}{2}</tex>, на третьем уровне <tex>-</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>\left\{\dfrac{1}{2}, \ \dfrac{1}{2}\right\}</tex>, можно влиять на количество элементов на верхних уровнях. Так, например, при использовании монеты с распределением <tex>\{p,q\}</tex> (с вероятностью <tex>p</tex> выпадает «Орёл») математическое ожидание количества элементов на уровне <tex>k</tex> равно <tex dpi=150>n q\cdot p^k</tex>, на каждом следующем уровне будет в среднем в <tex>q</tex> раз больше элементов. Таким образом, время поиска будет равно <tex>O\left(\dfrac{k}{q} + nq^k\right)</tex>. Соответственно при честной монетке и <tex>\log(n)</tex> уровней получаем оценку, полученную ранее.
Для крайних распределений:
* <tex>\{0, 1\}</tex> {{---}} <tex>O(k+n)</tex>
'''void''' insert ('''list''' skip_list, '''K''' key, '''T''' data) <font color=darkgreen>// Обёрточка</font>
insert(skip_list.head, key, data)
===Удаление элемента===
==Применение==
Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ.* Быстрая вставка элемента, поскольку не требуется каким-либо образом изменять другие элементы (только предыдущий элемент)* Базы данныхПроще реализовать, чем сбалансированные деревья или хеш-таблицы* Распределённые вычисления и p2pСледующий элемент достаётся за <tex>O(1)</tex>* Масштабируемые параллельные приоритетные очереди и словариЛегко модифицировать под различные задачиВ вычислительной геометрии широко применяются структуры на основе списка с пропусками.
==См. также==
*[[Список]]
*[[Рандомизированное бинарное дерево поиска]]
*[[Поисковые структуры данных]]
==Источники информации==
*[http://igoro.com/archive/skip-lists-are-fascinating/ igoro.com — Skip lists are fascinating]
*[https://link.springer.com/chapter/10.1007/BFb0028258 springer.com — The interval skip list]
*[http://ticki.github.io/blog/skip-lists-done-right/ ticki.github.io — Skip Lists: Done Right]
[[Категория: Структуры данных]]