142
правки
Изменения
→Метод «толстых» узлов
В примере выше в этом «толстом» узле будет храниться первая версия <tex>V_1</tex>, у которой <tex>a=3</tex> и вторая версия <tex>V_2</tex>, у которой <tex>a=4</tex>. Если далее последуют еще какие-то изменения (например, поле <tex>b</tex> нашего узла станет равно <tex>5</tex>) сделаем еще одну версию структуры данных — <tex>V_3</tex>.
Чтобы быстро найти нужную версию в списке версий, хранящихся в «толстом» узле, нужно хранить их в виде дерева. Тогда мы сможем за логарифм найти нужную версию и к ней обратиться. Значит все операции, которые будут производиться на этой структуре данных, будут домножаться на логарифм от числа версий.
Структура толстого узла может быть и другой: к каждой вершине можно хранить лог ее изменений, в который записывается версия, в которой произошло изменение, а также само изменение. Лог может быть организован по-разному. Обычно делают отдельный лог для каждого поля этой вершины. Когда что-то меняется в вершине, то в лог соответствующего поля записывается это изменение и номер версии, с которой данное изменение произошло. Когда нужно обратиться к старой версии, то двоичным поиском ищут в логе последнее изменение до этой версии и находят нужное значение.
Метод ''fat node'' дает замедление <tex> \log t</tex>, где <tex>t</tex> — число изменений структуры данных; памяти требуется <tex>n+t</tex>, где <tex>n</tex> — число вершин в структуре данных.
==Преобразование списка в персистентный за O(1)==
