Список с пропусками
Список с пропусками (skip-list) — одна из вероятностных структур данных, на ряде параллельных отсортированных связных списков с эффективностью, сравнимой с бинарными деревьями поиска. Все операции со списком с пропусками осуществляются за с большой вероятностью.
Отсортированный связный список является простейшей структурой со временем поиска . Одним из способов улучшить асимптотику данной структуры является добавление дополнительного уровня, обеспечивающего быстрый доступ через несколько элементов.
Операции над структурой
Поиск элемента
Допустим, что в нашем списке с пропусками существуют два уровня: , в котором содержатся все элементы и , в котором присутствует только часть из них. Между одинаковыми элементами этих двух списков существуют ссылки.
В таком случае алгоритм поиска в этой структуре будет представлять из себя следующие операции:
- Начинаем поиск элемента в верхнем левом углу
- Передвигаться будем по списку , пока значение в следующей ячейке меньше или равно ключу
- Переместиться в нижний уровень и продолжить аналогичный метод поиска по списку
Тогда время работы алгоритма поиска будет зависеть от количества элементов на уровне . Представим, что на этот уровень у нас случайным образом попало несколько элементов. Следовательно в худшем случае поиска мы получим следующую оценку на время работы:
Минимизируя, мы получаем, что
В итоге время за которое мы найдем элемент в списке с пропусками с двумя уровнями будет равняться:
Делая аналогичные подсчеты для списков с пропусками, в которых содержится больше уровней, получаем:
- Для трех уровней:
- Для четырех уровней:
- Для пяти уровней:
- Для уровней:
В списках с пропусками, в которых содержится уровней будет себя вести очень похоже на сбалансированные бинарные деревья поиска. В идеальной данной структуре соотношение между соседними уровнями будет равняться двум. Поиск в списке с пропусками будет осуществляться за асимптотическое время .
Вставка элемента
Для вставки элемента в список с пропусками, нам необходимо выполнить следующие шаги:
- Найти с помощью алгоритма поиска позицию, куда нам надо вставить этот элемент
- Вставить наш элемент в нижний уровень списка с пропусками
- «Подбросить монетку» и в зависимости от результата протолкнуть элемент на уровень выше
- Повторять предыдущий шаг до тех пор, пока у нас «подброс монетки» дает положительный результат
Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется , на третьем уровне и т.д. На уровне у нас окажется один элемент. Ну и соответственно вероятности попасть элементу на второй уровень — это , на третий и т.д. Вероятность попасть на уровень равна
Удаление элемента
Алгоритм удаления достаточно тривиален.
- Найти удаляемый элемент
- Удалить его со всех уровней
Псевдокод
const float P = 0.5
int random_level()
int lvl = (int)(log(frand())/log(1.-P))
return lvl < MAX_LEVEL ? lvl : MAX_LEVEL
boolean Find (int key)
SkipNode x = header
for (int i = level; i >= 0; i--)
while (x.forward[i] != NULL && x.forward[i].value < key)
x = x.forward[i]
x = x.forward[0]
return x != NULL && x.value == key
void Insert(int value)
SkipNode x = header
SkipNode update
update.assign(MAX_LEVEL + 1, 0)
for (int i = level; i >= 0; i--)
while (x.forward[i] != NULL && x.forward[i].value < value)
x = x.forward[i]
update[i] = x
x = x.forward[0]
if (x == NULL || x.value != value)
int lvl = random_level()
if (lvl > level)
for (int i = level + 1; i <= lvl; i++)
update[i] = header
level = lvl
x = new SkipNode(lvl, value)
for (int i = 0; i <= lvl; i++)
x.forward[i] = update[i].forward[i]
update[i].forward[i] = x
void Erase(int value)
SkipNode x = header
SkipNode update
update.assign(MAX_LEVEL + 1, 0)
for (int i = level; i >= 0; i--)
while (x.forward[i] != NULL && x.forward[i].value < value)
x = x.forward[i]
update[i] = x
x = x.forward[0]
if (x.value == value)
for (int i = 0; i <= level; i++)
if (update[i].forward[i] != x)
break
update[i].forward[i] = x.forward[i];
delete x
while (level > 0 && header.forward[level] == NULL)
level--
