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