Изменения

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

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

6 байт добавлено, 22:32, 18 апреля 2015
Преобразование списка в персистентный за O(1)
Пусть мы хотим добавить еще один элемент между узлами <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|700px]]
Будем называть узел полным, если у него есть вторая версия. Если мы хотим вставить новый элемент в середину списка (на рисунке ниже он обозначен зеленым цветом), мы должны склонировать все полные узлы слева и справа от места добавления нового узла, дойти до ближайших элементов, у которых нет второй версии и добавить им вторую версию.
Анонимный участник

Навигация