390
правок
Изменения
Нет описания правки
==Операции над структурой==
===Поиск элемента===
Допустим, что в нашем списке с пропусками существуют <tex>k</tex> уровней, при этом первым уровнем <tex>L_1</tex> будет исходный список.
В таком случае алгоритм поиска в этой структуре будет представлять из себя следующие операции:
# Начинаем поиск элемента в верхнем списке (<tex>L_k</tex>), рассмотрим первый элемент# Переходить Переходим к следующему элементу списка, пока значение в следующей ячейке меньше или равно ключу# Переместиться на один уровень вниз и перейти к пункту шагу <tex>2</tex>. Если рассматриваемый элемент находится мы уже были на нижнем первом уровне <tex>-</tex> выйти из поискапрекратить поиск.
Пример поиска числа <tex>8</tex> в списке из описания:
[[Файл:SkipListSearch.png]]
Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет <tex>\log{n}</tex> уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). Уровней всего <tex>\log{n}</tex>, откуда вытекает оценка времени поиска элемента в <tex>O(\log{n})</tex>.
Функция <tex>\mathtt{find}</tex> возвращает ссылку на элемент, значение которого не меньше <tex>\mathtt{key}</tex>. В случае, если все элементы в списке с пропусками меньше <tex>\mathtt{key}</tex>, то возвращается ссылка на конец списка с пропусками.
'''T''' find ('''list''' skip_list, '''K''' key)
'''node''' res
'''for''' (res = skip_list.head; res.ref != ''null''; res = res.ref) <font color=darkgreen>// Пока ещё не дошли до первого уровня </font> '''while''' res.key < key <font color=darkgreen>// Переходим к следующему элементуПока значение вершины меньше ключа</font> res = res.next() <font color=darkgreen>// Перейти к следующей вершине в текущем уровне</font> '''return''' res.data
===Вставка элемента===
