390
правок
Изменения
→Поиск элемента
==Операции над структурой==
===Поиск элемента===
[[Файл:SkipListSearch.png|thumb|600px|Пример поиска числа <tex>8</tex>]]
Допустим, что в нашем списке с пропусками существуют <tex>k</tex> уровней, при этом первым уровнем будет исходный список.
В таком случае алгоритм поиска в этой структуре будет представлять из себя следующие операции:
# Начинаем поиск элемента в самом верхнем списке(<tex>k</tex>-ом) уровне# Переходим к следующему элементу списка, пока значение в следующей ячейке меньше или равно ключу
# Переместиться на один уровень вниз и перейти к шагу <tex>2</tex>. Если мы уже были на первом уровне <tex>-</tex> прекратить поиск.
Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет <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 ('''node''' res, '''K''' key)
'''while''' res.key < key <font color=darkgreen>// Пока значение вершины меньше ключа</font>
res = res.next() <font color=darkgreen>// Перейдём к следующей вершине в текущем уровне</font>
'''if''' res.down = ''null'' <font color=darkgreen>// Если мы находимся на первом уровне</font>
'''return''' res <font color=darkgreen>// Мы нашли искомый элемент</font>
'''return''' find(res.down, key) <font color=darkgreen>// Иначе спустимся на один уровень ниже</font>
===Вставка элемента===
