390
правок
Изменения
м
→Вставка элемента
Отдельно стоит обработать случай, когда вставка нового элемента увеличивает число уровней. Тогда необходимо создать ещё один отсортированный список, в котором будет всего один текущий элемент, и не забыть присвоить списку с пропусками новую ссылку на верхний уровень. Будем считать, что вставка каждого нового элемента увеличивает число уровней не более чем на один.
Заметим, что вставка элемента <tex>-</tex> поиск элемента и за <tex>O(1)</tex> добавляем новый не более, чем в <tex>k</tex> уровней элемент. Итого время работы <tex>O(k \log_k{n})</tex>.
====Псевдокод====
