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