24
правки
Изменения
м
Правка орфографии
В полностью персистентных структурах данных можно менять не только последнюю, но и любую версию структур данных, также к любой версии можно делать запросы.
Конфлюэнтные структуры данных позволяют объединять две структуры данных в одну (деревья поиска, которые можно сливать).
Функциональные структуры данных полностью персистентны по определению, так как в них запрещаются уничтожающие присваивания, т.е. любой переменной значение может быть присвоено только один раз и изменять значения переменных нельзя.
===Метод копирование пути===
Пусть есть [[АВЛ-дерево |сбалансированное дерево поиска]]. Все операции в нем делаются за <tex>O(h)</tex>, где <tex>h</tex> — высота дерева, а высота дерева <tex>O</tex> <tex>(\log n)</tex>, где <tex>n</tex> — количество вершин. Пусть необходимо сделать какое-то обновление в этом сбалансированном дереве, например, добавить очередной элемент, но при этом нужно не потерять старое дерево. Возьмем узел, в который нужно добавить нового ребенка. Вместо того чтобы добавлять нового ребенка, скопируем этот узел, к копии добавим нового ребенка, также скопируем все узлы вплоть до корня, из которых достижим первый скопированный узел вместе со всеми указателями. Все вершины, из которых измененный узел не достижим, мы не трогаем. Количество новых узлов всегда будет порядка логарифма. В результате имеем доступ к обоим обеим версиям дерева.
[[Файл:Копирование пути.png]]
Персистентные структуры данных используются при решении геометрических задач. Примером может служить [[Локализация в ППЛГ методом полос (персистентные деревья)|Point location problem]] — задача о местоположении точки. Задачи такого рода решаются в ''offline'' и ''online''. В ''offline''-задачах все запросы даны заранее и можно обрабатывать их одновременно. В ''online''-задачах следующий запрос можно узнать только после того, как найден ответ на предыдущий.
При решении ''offline''-задачи данный планарный граф разбивается на полосы вертикальными прямыми, проходящими через вершины многоугольников. Затем в этих полосах при помощи техники заметающей прямой ''(scane sweep line)'' ищется местоположение точки-запроса. При переходе из одной полосы в другую изменяется [[Дерево поиска, наивная реализация|сбалансированное дерево поиска]]. Если использовать частично персистентную структуру данных, то для каждой полосы будет своя версия дерева и сохранится возможность делать к ней запросы. Тогда ''Point location problem'' может быть решена в ''online''.
== См. также ==
