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