Изменения

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

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

11 байт добавлено, 08:26, 12 апреля 2015
Метод копирование пути
===Метод копирование пути===
Пусть есть [[АВЛ-дерево |сбалансированное дерево поиска]]. Все операции в нем делаются за <tex>O(h)</tex> от высоты , где h -- высота дерева, а высота дерева <tex>O</tex> от логарифма количества вершин. Пусть необходимо сделать какое-то обновление в этом сбалансированном дереве, например, добавить очередной элемент, но при этом нужно не потерять старое дерево. Возьмем узел, в который нужно добавить нового ребенка. Вместо того чтобы добавлять нового ребенка, скопируем этот узел, к копии добавим нового ребенка, также скопируем все узлы вплоть до корня, из которых достижим первый скопированный узел вместе со всеми указателями. Все вершины, из которых наш измененный узел не достижим, мы не трогаем. Количество новых узлов всегда будет порядка логарифма. В результате получим возможность иметь доступ к обоим версиям дерева обновременно.
[[Файл:Копирование пути.png]]
Анонимный участник

Навигация