Изменения

Сформулируем, что такое структура данных. Это набор узлов, в которых хранятся какие-то данные и эти узлы связаны ссылками. Классический пример структуры данных - [[Дерево поиска, наивная реализация|дерево]]. Рассмотрим, как методом копирования пути превратить дерево в персистентное.

Пусть нам нужно сделать какое-то обновление в дереве, например, добавить очередной элемент, но при этом мы не хотим потерять старое дерево. Возьмем узел, в который мы хотим добавить нового ребенка. Вместо того чтобы добавлять нового ребенка, мы скопируем этот узел, к копии добавим нового ребенка, также скопируем все узлы, из которых достижим первый скопированный нами узел вместе со всеми указателями. Все вершины, из которых наш измененный узел не достижим, мы не трогаем.

[[Файл:Копирование пути.png]]

Пусть в структуре данных есть узел, в котором нужно сделать изменения (например, на нашем рисунке в первой версии структуры данных есть поле <tex>a=3</tex>, а во второй версии это поле должно быть равно <tex>4</tex>), но при этом нужно сохранить доступ и к старой версии узла. В таком случае можно хранить их оба в большом комбинированном узле.

[[Файл:Метод толстых узлов.png|центр]] ‎