3622
правки
Изменения
м
→Метод копирование пути
Так как рассматривается сбалансированное дерево поиска, то поднимая вершину вверх при балансировке, нужно делать копии всех вершин, участвующих во вращениях, у которых изменились ссылки на детей. Таких всегда не более трех, поэтому ассимптотика <tex>O</tex> <tex>( \log n)</tex> не пострадает. Когда балансировка закончится, нужно дойти вверх до корня, делая копии вершин на пути.
Этот метод хорошо работает на [[Стек|стеке]], двоичных ([[Декартово дерево |декартовых]], [[Красно- черное дерево | красно-черных]]) деревьях. Но в случае преобразования [[Очередь| очереди]] в персистентную операция добавления будет очень дорогой, так как элемент добавляется в хвост очереди, который достижим из всех остальных элементов. Так же Также не выгодно применять этот метод и в случае, когда в структуре данных имеются ссылки на родителя.
===Метод «толстых» узлов===
