Изменения
→Получение полностью персистентных структур данных
Операция обновления в этом списке будет происходить так: в список версий добавляется два элемента – первый вносит изменение, а второй будет возвращать обратно значение предыдущей версии. Таким образом, каждая операция разбивается на две: первая делает изменение, а вторая его откатывает.
В ''change log'' «толстого» узла теперь будем добавлять два события: одно указывает на изменение, произошедшее в соответствующей версии, а другое на его отмену. События будут отсортированы по их порядку в списке версий с помощью ''List Order Maintenance''.
В какой-то момент <math>''change log</math> '' «толстого» узла переполнится. Тогда нужно клонировать этот узел и нижнюю половину изменений перенести в ''change log'' склонированного узла. Первую половину изменений применяем к исходной версии узла и сохраняем в качестве исходной в склонированном узле.
Получится два узла: первый отвечает за отрезок версий до операции последнего изменения, а второй после нее. Дальнейший порядок действий аналогичен тому, который использовался в общем методе построения частично персистентных структур данных.
Оценим амортизационное время работы этого алгоритма. Введем потенциал, равный числу полных узлов. Когда мы раздваиваем узел, мы уменьшаем число полных узлов на единицу.
== См. также ==
