Для того, чтобы вставить элемент в список с пропусками, нужно запустить рекурсивную функцию, которая в каждом из уровней найдёт позицию, где должен был стоять элемент. Если это первый уровень, то просто вставляем элемент в список, а также возвращаем результат броска монетки. Если же это не самый нижний уровень <tex>-</tex> то рекурсивно вызываем функцию. Если в результате броска монетки выпал «Орёл», то вставляем элемент в список текущего уровня, а также вернуть результат броска монетки. Если же выпала «Решка», то просто возвращаем такой же результат. Нужно также обработать тот случай, если на всех уровнях выпал «Орёл». В таком случае надо создать новый верхний уровень и вставить в него текущий элемент, а также вернуть ссылку на начало нового уровня.
Таким образом===Удаление элемента===Для того, чтобы удалить элемент из списка с пропусками необходимо вызвать рекурсивную функцию, которая в каждом уровне, подобно поиску, найдёт позицию, где должен был стоять элемент. Во время рекурсии если использовать честную монетуэто самый нижний уровень, то удаляем элемент из списка (не забывая при этом сохранить связность списка). Если это не это первый уровень, то математическое ожидание количества элементов рекурсивно вызовем функцию от уровня ниже, а также удалим элемент в текущем уровне. После удаления элемента могло так получить, что несколько верхних уровней перестали содержать какие-либо элементы, тогда необходимо удалить эти уровни (кроме первого), и не забыть вернуть ссылку на втором уровне равняется начало самого верхнего уровня. ==Использование нечестной монеты==Вместо честной монеты с распределением <tex>\left\{\dfrac{1}{2}, \ \dfrac{n1}{2}\right\}</tex>можно взять в качестве случайного источника нечестную монету с распределением <tex>\{p, q\}</tex> (с вероятностью <tex>p</tex> выпадает «Орёл»). Тогда математическим ожиданием количества элементов на третьем уровне <tex>-k</tex> будет <tex>n \dfrac{n}{4}cdot p^k</tex> и т.д. На уровне Время поиска будет равно <tex>O\logleft( \dfrac{1}{p} \log_{\frac{1}{p}} {n}\right)</tex> у нас окажется один элемент. Cоответственно вероятности попасть элементу (на второй уровень — это <tex>i</tex>-ом уровне элементов будет почти в <tex>\dfrac{1}{2p}</tex>раз больше, чем на третий <tex>\dfrac{(i+1}{4})</tex> и т.д. Вероятность попасть -ом, значит на уровень каждом уровне пройдём не более <tex>\logdfrac{n1}{p}</tex> равна элементов, а уровней всего <tex>\dfraclog_{\frac{1}{p}}{n}</tex>).
Используя монетку с распределением отличным от <tex>\left\{\dfrac{1}{2}, \ \dfrac{1}{2}\right\}</tex>, можно влиять на количество элементов на верхних уровнях. Так, например, при использовании монеты с распределением <tex>\{p,q\}</tex> (с вероятностью <tex>p</tex> выпадает «Орёл») математическое ожидание количества элементов на уровне <tex>k</tex> равно <tex>n \cdot p^k</tex>. Таким образом, время поиска будет равно <tex>O\left( \dfrac{1}{p} \log_{\frac{1}{p}} {n} \right)</tex>.
Для крайних распределений:
* <tex>\{0, 1\}</tex> {{---}} <tex>O(n)</tex>
* <tex>\{1, 0\}</tex> {{---}} <tex>\infty</tex>
===Удаление элемента===
Для того, чтобы удалить элемент из списка с пропусками необходимо вызвать рекурсивную функцию, которая в каждом уровне, подобно поиску, найдёт позицию, где должен был стоять элемент. Во время рекурсии если это самый нижний уровень, то удаляем элемент из списка (не забывая при этом сохранить связность списка). Если это не это первый уровень, то рекурсивно вызовем функцию от уровня ниже, а также удалим элемент в текущем уровне. После удаления элемента могло так получить, что несколько верхних уровней перестали содержать какие-либо элементы, тогда необходимо удалить эти уровни (кроме первого), и не забыть вернуть ссылку на начало самого верхнего уровня.
==Применение==
