142
правки
Изменения
→Общий метод построения частично персистентных структур данных
Применим методы, описанные выше, в общем случае для абстрактной структуры данных. Пусть есть структура данных, у каждого узла которой количество указателей на этот узел не больше некоторой константы <tex>P</tex>. Если мы будем клонировать узел, нам важно будет знать, откуда на этот узел идут указатели, чтобы затем их переставить. Поэтому будем в каждом узле хранить обратные ссылки на те узлы, которые ссылаются на клонируемый нами узел.
Все узлы будем хранить в виде «толстых» узлов, в которых содержится начальная версия этого узла и список внесенных в него изменений (''change log'') длиной не больше <tex>2P</tex>.
Пусть мы хотим внести изменение в нашу структуру данных в узел <tex>X</tex>. Если у нас есть место в ''change log''есписке изменений, мы просто вносим наше изменение туда. Если ''change log'' заполнен, то мы клонируем узел <tex>X</tex>: берем стартовую версию узла, производим в ней все изменения, записанные в ''change log'', добавляем последнее изменение и делаем версию со свободным ''change log''омсписком изменений. Затем пройдем по обратным ссылкам от <tex>X</tex> и в ''change log'' каждого узла, ссылающегося на <tex>X</tex>, добавим изменение указателя начиная с этой версии структуры данных с <tex>X</tex> на <tex>X'</tex>.
[[Файл:Частичная персистентность.png]]
Оценим время работы этого алгоритма. Введем функцию потенциала, которая будет равна суммарному размеру всех ''change log''ов списков изменений в последней версии. Посмотрим, как меняется суммарный размер ''change log''овсписков изменений, когда мы совершаем одно изменение. Если ''change log'' был не полный, то мы просто добавляем туда один элемент, потенциал увеличится на единицу.Если ''change log'' был полный, то потенциал уменьшается на его размер ''change log''а, так как мы склонировали узел с пустым ''change log''омсписком изменений. После этого мы пошли по обратным ссылкам (их было <tex>P</tex> штук) и добавили в <tex>P</tex> узлов по одному значению. Таким образом амортизированное время работы будет <tex>O(1)</tex>.
==Получение полностью персистентных структур данных==
