Изменения

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