390
правок
Изменения
Нет описания правки
[[Файл:Skip list example.png|thumb|550px|Пример списка с пропусками]]
'''Список с пропусками''' (англ. ''skip list'') — вероятностная структура данных, позволяющая в среднем за <tex>O(\log(n))</tex> времени выполнять операции добавления, удаления и поиска элементов.
Структура данных основана на многоуровневом связном отсортированном списке. На самом нижнем (первом) уровне располагаются все элементы в отсортированном порядке. Дальше почти половина элементов таким же образом располагаются на втором, почти четверть <tex>-</tex> на третьем и так далее, но при этом известно, что если элемент расположен на <tex>i</tex>-ом уровне, то он также расположен на <tex>(i-1)</tex>-ом, <tex>(i-2)</tex>-ом и более низких уровнях.
