47
правок
Изменения
Исправлено определение, добавлено описание и картиночки.
'''Список с пропусками''' (''skip-list'') — одна из вероятностных структур вероятностная структура данных, основанная на ряде параллельных нескольких отсортированных связных списков с эффективностью, сравнимой с бинарными деревьями поиска. Все операции со списком с пропусками осуществляются за <tex>O(\log{n})</tex> с большой вероятностьюодносвязных списках.
Отсортированный связный список является простейшей структурой с временем поиска <tex>\Theta(n)</tex>. Одним из способов улучшить асимптотику данной структуры является добавление дополнительного уровняДобавление дополнительных уровней, обеспечивающего обеспечивающих быстрый доступ через несколько элементов, поможет улучшить асимптотику до <tex>\Theta(\log(n))</tex>. ==Описание==Список с пропусками строится на основе существующего односвязного отсортированного списка. [[Файл:SimpleList.png]] Добавив дополнительные уровни, каждый из которых представляет предыдущий уровень без нечетных элементов, мы получим возможность осуществлять поиск, вставку и удаление элементов подобно операциям с двоичным деревом поиска. Одинаковые элементы связаны между уровнями. Соответственно, асимптотика этих операций будет составлять <tex>\Theta(\log(n))</tex>. [[Файл:SkipList. png]]
==Операции над структурой==
# Передвигаться будем по списку <tex>L_2</tex>, пока значение в следующей ячейке меньше или равно ключу
# Переместиться в нижний уровень и продолжить аналогичный метод поиска по списку <tex>L_1</tex>
Пример поиска числа 8 в списке из описания:
[[Файл:SkipListSearch.png]]
Тогда время работы алгоритма поиска будет зависеть от количества элементов на уровне <tex>L_2</tex>. Представим, что на этот уровень у нас случайным образом попало несколько элементов. Следовательно в худшем случае поиска мы получим следующую оценку на время работы:
*[http://en.wikipedia.org/wiki/Skip_list Википедия — списки с пропусками(En)]
*[http://bit.ly/LiNe8M Курс kiev-clrs — Списки с пропусками]
*[http://igoro.com/archive/skip-lists-are-fascinating/ igoro.com — Skip lists are fascinating]
