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