Изменения

Перейти к: навигация, поиск

Персистентные структуры данных

4 байта добавлено, 21:45, 4 апреля 2015
Преобразование списка в персистентный за O(1)
==Преобразование списка в персистентный за O(1)==
Если скомбинировать методы ''path copiyng'' и ''fat node'', то получим универсальный метод, который позволит преобразовывать структуры данных в частично персистентные без дополнительного <tex>log</tex> логарифма памяти.
Пусть мы имеем [[Список| двусвязный список]] и хотим внести в него какое-то изменение, например, добавить узел <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>, как показано на рисунке.
Анонимный участник

Навигация