47
правок
Изменения
м
while x.forward[i] != NULL and x.forward[i].value < key x = x.forward[i] x = x.forward[0]
while x.forward[i] != NULL and x.forward[i].value < value x = x.forward[i] update[i] = x
for i = level + 1 to lvl update[i] = header level = lvl
for i = 0 to lvl x.forward[i] = update[i].forward[i] update[i].forward[i] = x
update.assign(MAX_LEVEL + 1, 0)
while x.forward[i] != NULL and x.forward[i].value < value x = x.forward[i] update[i] = x x = x.forward[0]
if update[i].forward[i] != x break update[i].forward[i] = x.forward[i];
level--
Увеличены дроби
Тогда время работы алгоритма поиска будет зависеть от количества элементов на уровне <tex>L_2</tex>. Представим, что на этот уровень у нас случайным образом попало несколько элементов. Следовательно в худшем случае поиска мы получим следующую оценку на время работы:
<tex> \approx \vert L_2\vert + \fracdfrac{\vert L_1\vert }{\vert L_2\vert } = \vert L_2\vert + \fracdfrac{n}{\vert L_2\vert }</tex>
Минимизируя, мы получаем, что <tex>\vert L_2 \vert ^ 2 = n</tex>
В итоге время за которое мы найдем элемент в списке с пропусками с двумя уровнями будет равняться:
<tex> \sqrt{n} + \fracdfrac{n}{\sqrt{n}} = 2 \sqrt{n}</tex>
Делая аналогичные подсчеты для списков с пропусками, в которых содержится больше уровней, получаем:
# Повторять предыдущий шаг до тех пор, пока у нас «подброс монетки» дает положительный результат
Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется <tex>\fracdfrac{n}{2}</tex>, на третьем уровне <tex>\fracdfrac{n}{4}</tex> и т.д. На уровне <tex>\log{n}</tex> у нас окажется один элемент. Ну и соответственно вероятности попасть элементу на второй уровень — это <tex>\fracdfrac{1}{2}</tex>, на третий <tex>\fracdfrac{1}{4}</tex> и т.д. Вероятность попасть на уровень <tex>\log{n}</tex> равна <tex>\fracdfrac{1}{n}</tex>
===Удаление элемента===
SkipNode x = header
for i = level to 0
return x != NULL && x.value == key
void Insert(int value)
SkipNode update
update.assign(MAX_LEVEL + 1, 0)
for i = level to 0
x = x.forward[0]
if x == NULL or x.value != value
int lvl = random_level()
if lvl > level
x = new SkipNode(lvl, value)
void Erase(int value)
SkipNode x = header
SkipNode update
for i = level to 0
if x.value == value
for i = 0 to level
delete x
while level > 0 or header.forward[level] == NULL
