3622
правки
Изменения
м
→Получение полностью персистентных структур данных
[[Файл:Полностью персистентные сд.png|900x700px]]
Получится два узла: первый отвечает за отрезок версий до операции последнего изменения, а второй {{---}} после нее. Дальнейший порядок действий аналогичен тому, который использовался в общем методе построения частично персистентных структур данных.
Оценим амортизационное время работы этого алгоритма. Введем функцию потенциала, равную числу полных узлов. Когда узел раздваивается, функция потенциала уменьшается на единицу, затем мы переставляем <tex>P</tex> ссылок, потенциал увеличивается на <tex>P</tex>, значит амортизационное время работы — <tex>O(1)</tex>.
