Изменения
Нет описания правки
'''Список с пропусками''' (англ. ''skip list'') — поисковая структура данных, реализующая интерфейс упорядоченного множества, позволяет производить операции поиска, добавления и удаления элемента в списке за достаточно малое время.
Поиск элемента в списке производится за <tex>\ThetaO(\log(n))</tex>; добавление и удаление элемета происходит за то же время, что и поиск, однако эти операции могут замедлить поиск в структуре.
Такая производительность достигается за счёт добавления новых уровней. При этом нижним уровнем является исходный список, а каждый следующий уровень - список, содержащий часть элементов предыдущего уровня со ссылками на эти элементы.
[[Файл:SimpleList.png]]
Добавив дополнительные уровни, каждый из которых представляет предыдущий уровень без нечетных элементов, мы получим возможность осуществлять поиск, вставку и удаление элементов подобно операциям с двоичным деревом поиска. Соответственно, асимптотика этих операций будет составлять <tex>\ThetaO(\log(n))</tex>.
[[Файл:SkipList.png]]
