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