1632
правки
Изменения
м
==Примечания== <references />* [[List order maintance]]
rollbackEdits.php mass rollback
{{Определение
|definition= '''Персистенные Персистентные структуры данных''' (англ.''persistent data structure'') — это структуры данных, которые при внесении в них каких-то изменений сохраняют все свои предыдущие состояния и доступ к этим состояниясостояниям.}}
==Уровни персистентности==
*полная (англ. ''full''),
*конфлюэнтная (англ. ''confluent''),
*фунциональная функциональная (англ. ''functional'').
В частично персистентных структурах данных к каждой версии можно делать запросы, но изменять можно только последнюю версию структуры данных.
В полностью персистентных структурах данных можно менять не только последнюю, но и любую версию структур данных, также к любой версии можно делать запросы.
Конфлюэнтные структуры данных позволяют объединять две структуры данных в одну (деревья поиска, которые можно сливать).
Функциональные структуры данных полностью персистентны по определению, так как в них запрещаются уничтожающие присваивания, т.е. любой переменной значение может быть присвоено только один раз и изменять значения переменных нельзя.
===Метод копирование пути===
Пусть есть [[АВЛ-дерево |сбалансированное дерево поиска]]. Все операции в нем делаются за <tex>O(h)</tex>, где <tex>h</tex> — высота дерева, а высота дерева <tex>O</tex> <tex>(\log n)</tex>, где <tex>n</tex> — количество вершин. Пусть необходимо сделать какое-то обновление в этом сбалансированном дереве, например, добавить очередной элемент, но при этом нужно не потерять старое дерево. Возьмем узел, в который нужно добавить нового ребенка. Вместо того чтобы добавлять нового ребенка, скопируем этот узел, к копии добавим нового ребенка, также скопируем все узлы вплоть до корня, из которых достижим первый скопированный узел вместе со всеми указателями. Все вершины, из которых измененный узел не достижим, мы не трогаем. Количество новых узлов всегда будет порядка логарифма. В результате имеем доступ к обоим обеим версиям дерева.
[[Файл:Копирование пути.png]]
Этот метод хорошо работает на [[Стек|стеке]], двоичных ([[Декартово дерево |декартовых]], [[Красно- черное дерево | красно-черных]]) деревьях. Но в случае преобразования [[Очередь| очереди]] в персистентную операция добавления будет очень дорогой, так как элемент добавляется в хвост очереди, который достижим из всех остальных элементов. Также не выгодно применять этот метод и в случае, когда в структуре данных имеются ссылки на родителя.
==== Реализация на основе дерева отрезков ====
На основе дерева отрезков можно построить полностью персистентную структуру данных.
Для реализации персистентного дерева отрезков удобно несколько изменить структуру дерева. Для этого будем использовать явные указатели <tex>L</tex> и <tex>R</tex> для дочерних элементов. Кроме того, заведем массив <tex>roots[]</tex>, в котором <tex>roots[i]</tex> указывает на корень дерева отрезков версии <tex>i</tex>
Для построения персистентного дерева отрезков из <tex>n</tex> элементов необходимо применить <tex>n</tex> раз операцию добавления элемента к последней версии дерева. Для того, чтобы добавить новый элемент к <tex>k</tex>-ой версии дерева, необходимо проверить, является ли оно полным бинарным. Если да, то создадим новый корень, левым сыном сделаем <tex>roots[k]</tex>. Иначе, сделаем копию корня исходной версии. Добавим корень в конец массива корней. Далее, спускаясь от корня к первому свободному листу, будем создавать несуществующие узлы и клонировать существующие. После этого в новой ветке необходимо обновить значение функции и некоторые указатели дочерних элементов. Поэтому, возвращаясь из рекурсии, будем менять один указатель на только что созданную или скопированную вершину, а также обновим значение функции, для которой строилось дерево. После этой операции в дереве появится новая версия, содержащая вставленный элемент.
Для того, чтобы изменить элемент в персистентном дереве отрезков, необходимо сделать следующие действия: спустимся в дереве от корня нужной версии до требуемого элемента, скопируем его, изменим значение, и, поднимаясь по дереву, будем клонировать узлы. При этом необходимо менять указатель на одного из детей на узел, созданный при предыдущем клонировании. После копирования корня, добавим новый корень в конец массива корней.
[[Файл:persist.png]]
Здесь изображено персистентное дерево отрезков с операцией минимум, в котором изначально было 3 вершины. Сперва к нему была добавлена вершина со значением 2, а потом изменена вершина со значением 7. Цвет ребер и вершин соответствует времени их появления. Синий цвет элементов означает, что они были изначально, зеленый - что они появились после добавления, а оранжевый - что они появились после изменения элемента.
===Метод «толстых» узлов===
==Получение полностью персистентных структур данных==
Для полностью персистентных структур данных применить описанный выше метод преобразования не получится, так как история создания версий не линейна и нельзя отсортировать изменения по версиям, как в частично персистентных структурах данных.
Пусть мы храним историю изменения версий в виде дерева. Сделаем[[Обход в глубину, цвета вершин| обход этого дерева в глубину]]. В порядке этого обхода запишем, когда мы входим, а когда выходим из каждой версии. Эта последовательность действий полностью задает дерево, сделаем из нее список. Когда после какой-то версии (на рисунке ниже это версия <tex>6</tex>) добавляется новая версия структуры данных (на рисунке версия <tex>8</tex>), мы вставляем два элемента в список (на рисунке это <tex>+8</tex> и <tex>-8</tex>) после входа, но до выхода из той версии, когда пришло произошло изменение (то есть между
элементами <tex>+6</tex> и <tex>-6</tex>). Первый элемент вносит изменение, а второй будет возвращать обратно значение предыдущей версии. Таким образом, каждая операция разбивается на две: первая делает изменение, а вторая его откатывает.
[[Файл:Полная персистентность.png]]
Для реализации описанного в предыдущем пункте метода преобразования структур данных в полностью персистентные нам нужен такой список, который поддерживает операции <tex>\mathrm{insert After(p,q})</tex> (вставить <tex>q</tex> после <tex>p</tex>) и <tex>\mathrm{order(p,q)}</tex> (должен уметь отвечать на запросы вида "<tex>p</tex> лежит в этом списке до <tex>q</tex>"). <tex>\mathrm{order(p,q)}</tex> возвращает <tex>1</tex>, если <tex>p</tex> лежит до <tex>q</tex> и <tex>0</tex> иначе. Это список с поддержкой запроса о порядке [[List order maintenance|''List Order Maintenance'' <ref>[http://www.cs.au.dk/~gerth/aa11/slides/order.pdf List Order Maintenance]</ref>], который обе эти операции делает за <tex>O(1)</tex>.
В ''change log'' «толстого» узла теперь будем добавлять два события: одно указывает на изменение, произошедшее в соответствующей версии, а другое на его отмену. События будут добавляться в ''change log'' не по номерам версий, а по их порядку в списке версий ''List Order Maintenance''.
Персистентные структуры данных используются при решении геометрических задач. Примером может служить [[Локализация в ППЛГ методом полос (персистентные деревья)|Point location problem]] — задача о местоположении точки. Задачи такого рода решаются в ''offline'' и ''online''. В ''offline''-задачах все запросы даны заранее и можно обрабатывать их одновременно. В ''online''-задачах следующий запрос можно узнать только после того, как найден ответ на предыдущий.
При решении ''offline''-задачи данный планарный граф разбивается на полосы вертикальными прямыми, проходящими через вершины многоугольников. Затем в этих полосах при помощи техники заметающей прямой ''(scane sweep line)'' ищется местоположение точки-запроса. При переходе из одной полосы в другую изменяется [[Дерево поиска, наивная реализация|сбалансированное дерево поиска]]. Если использовать частично персистентную структуру данных, то для каждой полосы будет своя версия дерева и сохранится возможность делать к ней запросы. Тогда ''Point location problem'' может быть решена в ''online''.
== См. также ==
* [[Персистентная очередь]]
* [[Персистентный дек]]
== Источники информации ==
