Изменения

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