390
правок
Изменения
Нет описания правки
Если в качестве случайного источника использовать честную монету, то тогда если в списке будет <tex>n</tex> элементов, то количество уровней в среднем будет равно <tex>\log{n}</tex>. Тогда на последнем уровне будет не более двух элементов, а на каждом следующем будет почти в два раза больше. Тогда на каждом уровне мы проверим не более двух элементов (если бы на каком-нибудь уровне проверили три элемента, то в среднем это значило, что мы могли пройти на верхнем уровне на один элемент больше). Уровней всего <tex>\log{n}</tex>, откуда вытекает оценка времени поиска элемента в <tex>O(\log{n})</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()
'''return''' res.data
===Вставка элемента===
* <tex>key</tex> {{---}} ключ типа K
Вставка:
<code>
