Изменения

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

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

9 байт убрано, 07:52, 7 апреля 2015
→‎Преобразование списка в персистентный за O(1)
Пусть мы имеем [[Список| двусвязный список]] и хотим внести в него какое-то изменение, например, добавить узел <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>, как показано на рисунке.
Эта структура Этот алгоритм работает такследующим образом. Например, мы знаем, что текущая первая версия и идем . Идем по нашему списку слева направо от первого узла к узлу <tex>X</tex>, а затем хотим нужно перейти к следующему узлу. В «толстом» узле <tex>X</tex> мы выбираем нужную нам (первую) версию и далее следуем по ссылкам.
[[Файл:Список1.png|700px]]
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/45360»

Навигация