390
правок
Изменения
→Вставка элемента
Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется <tex>\dfrac{n}{2}</tex>, на третьем уровне <tex>-</tex> <tex>\dfrac{n}{4}</tex> и т.д. На уровне <tex>\log{n}</tex> у нас окажется один элемент. Ну и соответственно вероятности попасть элементу на второй уровень — это <tex>\dfrac{1}{2}</tex>, на третий <tex>\dfrac{1}{4}</tex> и т.д. Вероятность попасть на уровень <tex>\log{n}</tex> равна <tex>\dfrac{1}{n}</tex>.
Используя монетку с распределением отличным от <tex>\left\{\dfrac{1}{2}, \ \dfrac{1}{2}\right\}</tex>, можно влиять на количество элементов на верхних уровнях. Так, например, при использовании монеты с распределением <tex>\{p,q\}</tex> (с вероятностью <tex>p</tex> выпадает «Орёл») математическое ожидание количества элементов на уровне <tex>k</tex> равно <tex dpi=150>n q\cdot p^k</tex>, на каждом следующем уровне будет в среднем в <tex>q</tex> раз больше элементов. Таким образом, время поиска будет равно <tex>O\left(\dfrac{k}{q} + nq^k\right)</tex>. Соответственно при честной монетке и <tex>\log(n)</tex> уровней получаем оценку, полученную ранее.
Для крайних распределений:
* <tex>\{0, 1\}</tex> {{---}} <tex>O(k+n)</tex>
'''void''' insert ('''list''' skip_list, '''K''' key, '''T''' data) <font color=darkgreen>// Обёрточка</font>
insert(skip_list.head, key, data)
===Удаление элемента===
