Изменения

Перейти к: навигация, поиск

Персистентные структуры данных

776 байт добавлено, 19:55, 17 апреля 2015
Метод копирование пути
===Метод копирование пути===
Пусть есть [[АВЛ-дерево |сбалансированное дерево поиска]]. Все операции в нем делаются за <tex>O(h)</tex>, где h — высота дерева, а высота дерева <tex>O</tex> <tex>( \log n)</tex>, где <tex>n</tex> — количество вершин. Пусть необходимо сделать какое-то обновление в этом сбалансированном дереве, например, добавить очередной элемент, но при этом нужно не потерять старое дерево. Возьмем узел, в который нужно добавить нового ребенка. Вместо того чтобы добавлять нового ребенка, скопируем этот узел, к копии добавим нового ребенка, также скопируем все узлы вплоть до корня, из которых достижим первый скопированный узел вместе со всеми указателями. Все вершины, из которых наш измененный узел не достижим, мы не трогаем. Количество новых узлов всегда будет порядка логарифма. В результате получим возможность иметь доступ к обоим версиям дерева обновременноодновременно.
[[Файл:Копирование пути.png]] Так как рассматривается сбалансированное дерево поиска, то поднимая вершину вверх при балансировке нужно делать копии всех вершин участвующих во вращениях у которых изменились ссылки на детей. Таких всегда не более трех, поэтому ассимптотика <tex>O</tex> <tex>( \log n)</tex> не пострадает. Когда балансировка закончится нужно дойти вверх до корня делая копии вершин на пути. Получается копирование пути с некоторой его окрестностью.
Этот метод хорошо работает на [[Стек|стеке]], двоичных ([[Декартово дерево |декартовых]], [[Красно- черное дерево | красно-черных]]) деревьях. Но в случае преобразования [[Очередь| очереди]] в персистентную операция добавления (англ.''push'') будет очень дорогой, так как элемент добавляется в хвост очереди, который достижим из всех остальных элементов. Так же не выгодно применять этот метод и в случае, когда в структуре данных имеются ссылки на родителя.
142
правки

Навигация