142
правки
Изменения
→Преобразование списка в персистентный за O(1)
Будем называть узел полным, если у него есть вторая версия. Если мы хотим вставить новый элемент в середину списка, мы должны склонировать все полные узлы слева и справа от места добавления нового узла, дойти до ближайших элементов, у которых нет второй версии и добавить им вторую версию.
Оценим амортизационное время работы такого алгоритма. У нас частично персистентная структура данных, мы изменяем только ее последнюю версию. Примем функцию потенциала равной числу полных узлов в последней версии. Если мы склонировали <tex>k</tex> узлов, то количество полных узлов в последней версии уменьшится на <tex>k</tex>, и еще два узла мы добавим (по одному слева и справа). Таким образом, амортизационное время работы по добавлению элемента будет <tex>O(1)</tex>.
==Общий метод построения частично персистентных структур данных==
