3622
правки
Изменения
м
→Общий метод построения частично персистентных структур данных
==Общий метод построения частично персистентных структур данных==
Применим методы, описанные выше, в общем случае для абстрактной структуры данных. Пусть есть структура данных, у каждого узла которой количество указателей на этот узел не больше некоторой константы <tex>P</tex>. Если мы будем клонировать узел, нам важно будет знать, откуда на этот узел идут указатели, чтобы затем их переставить. Поэтому будем в каждом узле хранить обратные ссылки на те узлы, которые ссылаются на клонируемый нами узел.
Все узлы будем хранить в виде «толстых» узлов, в которых содержится начальная версия этого узла и список внесенных в него изменений (англ. ''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>.
