Изменения
→Удаление элемента без пометок
{{Утверждение
|about=о времени работы
|statement=Асимптотически время работы <tex>\mathrm{delete}</tex> и <tex>\mathrm{find}</tex> совпадают
|proof=
Заметим что указатель <tex>j</tex> в каждой итерации перемещается вперёд на <tex>q</tex> (с учётом рекурсивных вызовов <tex>\mathrm{delete}</tex>). То есть этот алгоритм последовательно пройдёт по цепочке от удаляемого элемента до последнего - с учётом вызова <tex>\mathrm{find}</tex> собственно для нахождения удаляемого элемента, мы посетим все ячейки цепи.
}}
Теперь докажем почему этот алгоритм работает. Собственно нам требуется сохранение трёх условий.
* В редактируемой цепи не остаётся дырок
Докажем по индукции. Если на данной итерации мы просто удаляем элемент (база), то после него ничего нет, всё верно. Если же нет, то вызванный в конце <tex>\mathrm{delete}</tex> (см. псевдокод) заметёт созданную дыру (скопированный элемент), и сам, по предположению, новых не создаст.
* Элементы, которые уже на своих местах, не должны быть сдвинуты.
Это учтено.
