390
правок
Изменения
→Вставка элемента
===Вставка элемента===
Для вставки элемента того, чтобы вставить элемент в список с пропусками, нам необходимо выполнить следующие шаги: # Найти с помощью алгоритма поиска нужно запустить рекурсивную функцию, которая в каждом из уровней найдёт позицию, где мог бы находиться должен был стоять элемент.# Вставить наш Если это первый уровень, то просто вставляем элемент в текущий уровень списка с пропусками# Подбросить монетусписок, а также возвращаем результат броска монетки.# Если выпал «Орёл» то перейти на же это не самый нижний уровень выше и вернуться к шагу <tex>2-</tex>то рекурсивно вызываем функцию. Если в результате броска монетки выпал «Орёл», то вставляем элемент в список текущего уровня, а также вернуть результат броска монетки. Если же выпала «Решка», то просто возвращаем такой же результат. Нужно также обработать тот случай, если на всех уровнях выпал «Орёл». В таком случае надо создать новый верхний уровень и вставить в него текущий элемент, иначе закончить операцию вставки элементаа также вернуть ссылку на начало нового уровня.
Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется <tex>\dfrac{n}{2}</tex>, на третьем уровне <tex>-</tex> <tex>\dfrac{n}{4}</tex> и т.д. На уровне <tex>\log{n}</tex> у нас окажется один элемент. Cоответственно вероятности попасть элементу на второй уровень — это <tex>\dfrac{1}{2}</tex>, на третий <tex>\dfrac{1}{4}</tex> и т.д. Вероятность попасть на уровень <tex>\log{n}</tex> равна <tex>\dfrac{1}{n}</tex>.
* <tex>\{0, 1\}</tex> {{---}} <tex>O(n)</tex>
* <tex>\{1, 0\}</tex> {{---}} <tex>\infty</tex>
===Удаление элемента===
