142
правки
Изменения
→Преобразование списка в персистентный за O(1)
Этот алгоритм работает следующим образом. Например, текущая первая версия. Идем по списку слева направо от первого узла к узлу <tex>X</tex>, а затем нужно перейти к следующему узлу. В «толстом» узле <tex>X</tex> выбираем нужную (первую) версию и далее следуем по ссылкам.
[[Файл:Список1.png|700px600px]]
Пусть мы хотим добавить еще один элемент между узлами <tex>X</tex> и <tex>Y</tex>, но проблема в том, что у <tex>X</tex> и <tex>Y</tex> уже есть вторая версия, добавлять третью невыгодно. Поэтому более двух версий добавлять не будем. Используем метод копирования пути. Скопируем узлы <tex>X</tex> и <tex>Y</tex>, начиная с их третьей версии, и свяжем новые узлы с исходным списком. Для этого добавим вторые версии предыдущему перед <tex>X</tex> и последующему после <tex>Y</tex> узлам и свяжем эти узлы соответствующими ссылками. Так все версии остаются доступными.
[[Файл:Список2.png]]
Будем называть узел полным, если у него есть вторая версия. Если мы хотим вставить новый элемент в середину списка(на рисунке ниже он обозначен зеленым цветом), мы должны склонировать все полные узлы слева и справа от места добавления нового узла, дойти до ближайших элементов, у которых нет второй версии и добавить им вторую версию. [[Файл:Аморанализ.png|700px]]
Оценим амортизационное время работы такого алгоритма. У нас частично персистентная структура данных, мы изменяем только ее последнюю версию. Примем функцию потенциала равной числу полных узлов в последней версии. Если мы склонировали <tex>k</tex> узлов, то количество полных узлов в последней версии уменьшится на <tex>k</tex>, и еще два узла мы добавим (по одному слева и справа). Таким образом, амортизационное время работы по добавлению элемента будет <tex>O(1)</tex>.
