142
правки
Изменения
→Преобразование списка в персистентный за O(1)
==Преобразование списка в персистентный за O(1)==
Если скомбинировать методы ''path copiyng'' и ''fat node'', то получим универсальный метод, который позволит преобразовывать структуры данных в частично персистентные без дополнительного логарифма памятии времени.
Пусть мы имеем [[Список| двусвязный список]] и хотим внести в него какое-то изменение, например, добавить узел <tex>Z</tex> между узлами <tex>X</tex> и <tex>Y</tex>, то есть при переходе из версии <tex>1</tex> в версию <tex>2</tex> добавим в двусвязный список узел <tex>Z</tex>.
Применим метод «толстых» узлов. Для этого в узлы <tex>X</tex> и <tex>Y</tex> добавим вторую версию и изменим ссылку, следующую из <tex>X</tex>, и предыдущую перед <tex>Y</tex>, как показано на рисунке.
