Изменения
→Получение полностью персистентных структур данных
Получится два узла: первый отвечает за отрезок версий до операции последнего изменения, а второй после нее. Дальнейший порядок действий аналогичен тому, который использовался в общем методе построения частично персистентных структур данных.
Оценим амортизационное время работы этого алгоритма. Введем потенциал, равный числу полных узловсуммарному размеру нижних половин списков изменений во всех версиях. Когда мы раздваиваем узел, мы уменьшаем число полных узлов потенциал на единицуполовину размера списка изменений (в нашем примере это <tex>2P</tex>), затем мы переставляем <tex>P</tex> ссылок, потенциал увеличивается на <tex>P</tex>, значит амортизационное время работы - <tex>O(1)</tex>.
== См. также ==
