74
правки
Изменения
→Вставка точки
=== Вставка точки ===
Вставим точку в дерево, как в обычное сбалансированное дерево поиска. Из-за балансировки мосты в <tex>O(\log{n})</tex> вершинах дерева могут оказаться неактуальными, поэтому, возвращаясь по пути вверх до корня, будем пересчитывать мосты в таких вершинах методом, описанным выше, пользуясь тем, что всё поддерево рассматриваемой вершины уже содержит корректную информацию. Каждый пересчет моста требует <tex>O(\log{n})</tex> времени, откуда итоговая асимптотика вставки: <tex>O(\log^2{n})</tex>.
=== Удаление точки ===
