390
правок
Изменения
Нет описания правки
'''Список с пропусками''' (англ. ''skip list'') — вероятностная структура данных, позволяющая в среднем за <tex>O(\log(n))</tex> времени выполнять операции добавления, удаления и поиска элементов.
Структура данных основана на многоуровневом связном отсортированном списке. На самом нижнем (первом) уровне располагаются все элементы в отсортированном порядке. Дальше почти половина элементов таким же образом располагаются на втором, почти четверть <tex>-</tex> на третьем и так далее, но при этом известно, что если элемент расположен на каком-то уровнем <tex>iL_i</tex>-ом уровне, то он также соответственно расположен и на всех уровнях <tex>(i-1)L_j</tex>-ом, где <tex>(j < i-2)</tex>-ом и более низких уровнях.
==Построение==
