390
правок
Изменения
→Поиск элемента
# Переместиться на один уровень вниз и перейти к шагу <tex>2</tex>. Если мы уже на первом уровне <tex>-</tex> прекратить поиск и вернуть ссылку на текущую вершину
В конце алгоритма функция вернёт элемент, значение которого не меньше ключа <tex>\mathtt{key}</tex> или ссылку на хвост конец списка на первом уровне.
Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет <tex>\log{n}</tex> уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). Уровней всего <tex>\log{n}</tex>, откуда вытекает оценка времени поиска элемента в <tex>O(\log{n})</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>
Для того, чтобы найти элемент с ключом <tex>\mathtt{key}</tex> в списке с пропусками <tex>\mathtt{listskip}</tex> необходимо запустить <tex>\mathtt{find}</tex> следующим образом
find(listskip.head(), key)
===Вставка элемента===
