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

TL;DR

Персистентная структура данных (persistent data structure) сохраняет доступ ко всем своим предыдущим версиям: каждая операция создаёт новую версию, не разрушая старые. Наивный способ — копировать структуру целиком — стоит [math]\displaystyle{ \Theta(n) }[/math] на операцию и [math]\displaystyle{ \Theta(n^2) }[/math] на историю. Поэтому применяют разделение данных (sharing): три классических метода — path copying (копируем только путь до изменённого места, остальные поддеревья общие), fat nodes (каждое поле хранит историю значений по версиям) и node copying (узел копируется при заполнении, с ограничением входящей степени). Различают уровни персистентности: частичная, полная, функциональная и слитная (confluent, с объединением версий). Персистентность — основа функциональных языков, систем контроля версий, многоверсионных СУБД (MVCC), undo/redo и безопасного разделения данных между потоками. Конкретные реализации разобраны в персистентный-стек, персистентная-очередь и очередь-на-шести-стеках.

Свойство	Значение
Класс	Приём/семья структур, сохраняющих версии
Что общего	операция не разрушает прошлые состояния; новая версия = ссылка
Уровни	частичная, полная, функциональная, слитная
Методы	path copying, fat nodes, node copying, функциональная пересборка
Цена обновления	от [math]\displaystyle{ \Theta(n) }[/math] (копия) до [math]\displaystyle{ O(\log n) }[/math] (path copying); fat nodes — [math]\displaystyle{ O(1) }[/math] на обновление; node copying — [math]\displaystyle{ O(1) }[/math] аморт. при ограниченной входящей степени
Цена доступа к версии	[math]\displaystyle{ O(1) }[/math] по ссылке; материализация — [math]\displaystyle{ O(k) }[/math]
Память	[math]\displaystyle{ O(n) }[/math]–[math]\displaystyle{ O(n\log n) }[/math] при разделении против [math]\displaystyle{ \Theta(n^2) }[/math] при копировании
Ключевое требование	неизменяемость (или учёт версий) разделяемых узлов
Родственные	ретроактивные и кинетические структуры, MVCC
Где встречается	функциональные языки, Git, СУБД, геометрия, undo, параллельность

Определения

Персистентная структура данных — структура, поддерживающая доступ ко всем версиям, порождённым последовательностью операций. Противоположность — эфемерная (ephemeral) структура, хранящая лишь текущее состояние.

Версия (version) — состояние структуры после некоторого набора операций. Доступ к версии обычно осуществляется по ссылке на её «корень» (или по индексу) за [math]\displaystyle{ O(1) }[/math].

Уровни персистентности (см. рис. 1):

• частичная (partial) — изменять можно только самую новую версию, читать — любую;
• полная (full) — изменять и читать можно любую версию (версии образуют дерево);
• функциональная (functional) — каждая ячейка инициализируется один раз и не меняется; новая версия строится только из старых;
• слитная (confluent) — любую версию можно изменять и, кроме того, объединять две версии (merge); версии образуют ациклический граф (DAG).

Рис. 1. Уровни персистентности различаются тем, что разрешено менять и читать; функциональный — сильнейший по неизменяемости, слитный — по операциям.

Path copying (копирование пути). Обновление копирует только узлы вдоль пути от корня до изменяемого места; поддеревья, не лежащие на пути, разделяются между версиями. Применяется к деревьям.

Fat node (толстый узел). Каждое поле узла хранит не одно значение, а список пар (версия, значение), накапливаемый по мере изменения. Чтение поля на версии [math]\displaystyle{ v }[/math] — поиск последнего присваивания с номером [math]\displaystyle{ \le v }[/math].

Node copying (копирование узла). Узел копируется, когда его «слоты» для новых указателей заняты; копия и оригинал хранят списки версий указателей. Требует ограниченной входящей степени (bounded in-degree): у каждого узла не более [math]\displaystyle{ O(1) }[/math] входящих ссылок.

Функциональная пересборка. Новая версия строится целиком из старых данных (например, [math]\displaystyle{ b }[/math]-дерево пересобирается снизу вверх); проста, но стоит [math]\displaystyle{ O(n) }[/math].

Обозначения. [math]\displaystyle{ n }[/math] — размер структуры; [math]\displaystyle{ m }[/math] — число модификаций поля; [math]\displaystyle{ V }[/math] — число версий; [math]\displaystyle{ \log }[/math] — двоичный. «Ссылка на версию» — указатель на корень (или индекс).

Мотивация и интуиция

Обычные структуры эфемерны: массив, список или дерево хранят одно состояние, а операции его перезаписывают. Если нужна история, приходится либо заранее копировать структуру, либо реконструировать прошлое по журналу. Копирование даёт [math]\displaystyle{ \Theta(n) }[/math] на операцию и, при [math]\displaystyle{ n }[/math] версиях, [math]\displaystyle{ \Theta(n^2) }[/math] суммарной памяти (см. рис. 2). Для больших структур это неприемлемо.

Рис. 2. Полная копия на каждое изменение: [math]\displaystyle{ 1+2+\dots+n = \Theta(n^2) }[/math]; разделение данных снижает память до [math]\displaystyle{ O(n\log n) }[/math] для сбалансированного BST (для списка/стека — до [math]\displaystyle{ O(n) }[/math]).

Ключевая идея — не копировать то, что не изменилось. Меняя одно поле, мы затрагиваем лишь небольшую часть структуры; всё остальное можно переиспользовать — на неизменяемые части могут ссылаться и старая, и новая версии. Отсюда два больших подхода:

• Функциональный (immutable): узлы не меняются вовсе; изменение = создание новых узлов со ссылками на старые части. Пример — path copying.
• In-place: структура дополняется информацией о версиях, но сами «старые» данные остаются на месте. Примеры — fat nodes и node copying.

Зачем это нужно: функциональные языки (нет мутации), версионирование и undo, многоверсионные СУБД (читатель видит снапшот, писатель ему не мешает), вычислительная геометрия (история изменений), безопасное разделение данных между потоками. Подробности по конкретным структурам — в персистентный стек, персистентная очередь, декартово-дерево.

Устройство

Персистентная структура — это набор неизменяемых узлов (или узлов с версионной историей), связанных ссылками, и набор версий, каждая из которых задаётся ссылкой на свой корень. Обычно версия включает номер (или время), монотонно возрастающий.

Path copying

При обновлении (например, insert в дерево поиска) копируются узлы вдоль пути корень → лист, а не соседние поддеревья. Новая версия получает новый корень; старая продолжает ссылаться на нетронутые поддеревья. См. рис. 3: при вставке 55 копируются только узлы 50 и 70, а поддерево 30 остаётся общим.

Рис. 3. Копируется только путь вставки; поддеревья вне пути разделяются между версиями.

Цена: для сбалансированного дерева путь имеет длину [math]\displaystyle{ O(\log n) }[/math], значит, insert создаёт [math]\displaystyle{ O(\log n) }[/math] новых узлов и столько же времени. Память на одну операцию — [math]\displaystyle{ O(\log n) }[/math]; суммарно за [math]\displaystyle{ n }[/math] вставок — [math]\displaystyle{ O(n\log n) }[/math]. Доступ к любой версии — [math]\displaystyle{ O(1) }[/math] по её корню. Требование: узлы неизменяемы (иначе испортится старая версия).

Fat nodes и node copying

Если структура не дерево (или хочется экономить на копировании пути), применяют in-place методы (см. рис. 4). В fat node каждое поле хранит список значений по версиям; изменение — это добавление пары в конец списка. В node copying узел имеет фиксированное число слотов; когда они заполнены, создаётся копия, а список версий указывает, какая копия «актуальна» для версии.

Рис. 4. Fat nodes хранят историю в полях; node copying копирует узел при заполнении слотов (нужна ограниченная входящая степень).

Версии как дерево или граф

Для полной и слитной персистентности версии удобно представлять деревом (или DAG), где ребро — операция над версией (см. рис. 5). Это делает явной структуру истории и объясняет, почему амортизированные оценки «не переносятся»: одну и ту же дорогую операцию можно выполнить из разных версий.

Рис. 5. Частичная персистентность — линия, полная — дерево, слитная — DAG с операциями merge.

Операции и алгоритмы

Общих «операций» у класса нет — они определяются конкретной структурой. Но есть универсальные процедуры: обновление через path copying, чтение/запись fat-поля, доступ к версии. Все примеры ниже даны для персистентного бинарного дерева поиска (BST) как канонической структуры.

Операция: Insert через path copying

Идея. Спускаясь к месту вставки, каждый узел пути заменяем его копией с обновлённой ссылкой на изменённого ребёнка; у листа создаём новый узел. Поддеревья вне пути переиспользуются.

Пошаговое описание:

1. Если дерево пусто — вернуть версию из одного нового узла.
2. Спуститься по ключу: влево при [math]\displaystyle{ k \lt \text{key} }[/math], вправо при [math]\displaystyle{ k \gt \text{key} }[/math].
3. На обратном пути создать копию каждого узла пути, подставив обновлённого ребёнка.
4. Если ключ уже есть — вернуть узел без копирования (структура не меняется).

Инвариант. Каждый узел любой версии неизменяем; версия определяется ссылкой на корень; все поддеревья, не лежащие на пути, общие с предыдущей версией.

Операция Insert(v, k)
Вход:  версия v (корень дерева); k — ключ
Выход: новая версия v' (корень), содержащая k
Инвариант: v и v' — корректные BST; изменены только узлы пути
Сложность: O(h) времени и новых узлов (h — высота; O(log n) для сбалансированного)

1  if v = NIL
2      return новый узел ⟨k, NIL, NIL⟩
3  if k = v.key
4      return v                          # без изменений
5  if k < v.key
6      l' ← Insert(v.left, k)
7      if l' = v.left
8          return v                      # изменений не было
9      return новый узел ⟨v.key, l', v.right⟩
10 else
11     r' ← Insert(v.right, k)
12     if r' = v.right
13         return v
14     return новый узел ⟨v.key, v.left, r'⟩

Разбор. Дерево {50, 30, 70}; Insert(55) копирует 50 и 70, создаёт узел 55; поддерево 30 остаётся общим (рис. 3). Другая ветвь от той же версии (Insert(25)) не конфликтует: версии независимы.

Сложность. [math]\displaystyle{ O(h) }[/math]; для сбалансированного дерева [math]\displaystyle{ O(\log n) }[/math].

Крайние случаи. Совпадающий ключ не создаёт копий; пустое дерево — один новый узел.

Операция: Fat-Node Set и Get

Идея. Поле хранит список (версия, значение); Set добавляет пару, Get ищет последнее присваивание с номером [math]\displaystyle{ \le }[/math] запрошенного.

Операция Fat-Set(node, field, version, value)
Вход:  узел; поле; номер версии; значение
Сложность: O(1)

1  list[node][field].append((version, value))

Операция Fat-Get(node, field, version)
Вход:  узел; поле; номер версии
Выход: значение поля в этой версии
Сложность: O(log m) — двоичный поиск по истории длины m

1  h ← list[node][field]
2  return Value-At(h, version)          # последняя пара с version' ≤ version

Разбор. Поле key менялось в версиях 1 и 4: [(1,5), (4,8)]. Fat-Get(·, 3) вернёт 5, Fat-Get(·, 4) и позже — 8.

Крайние случаи. Запрос версии раньше первого присваивания — ошибка (значения ещё не было).

Замечание: доступ к версии

Идея. Версия — это ссылка на корень; доступ [math]\displaystyle{ O(1) }[/math]. Материализация (выписывание всех элементов) — [math]\displaystyle{ O(k) }[/math] для версии из [math]\displaystyle{ k }[/math] элементов. Обновление любой версии даёт новую ветвь.

Сводная таблица сложности

Метод	Обновление	Доступ к корню	Доступ к значению	Память на операцию	Условия
Полная копия	[math]\displaystyle{ \Theta(n) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math] по индексу	[math]\displaystyle{ \Theta(n) }[/math]	—
Path copying	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	сбалансированное дерево, узлы неизменяемы
Fat nodes	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(\log m) }[/math]	[math]\displaystyle{ O(1) }[/math]	история в полях
Node copying	[math]\displaystyle{ O(1) }[/math] аморт.	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math] аморт.	ограниченная входящая степень
Функциональная пересборка	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math] по индексу	[math]\displaystyle{ O(n) }[/math]	полная перестройка

Оговорки: доступ к корню версии — [math]\displaystyle{ O(1) }[/math] для всех методов; [math]\displaystyle{ O(\log m) }[/math] у fat nodes — это чтение поля, а не доступ к версии. Память указана на операцию; суммарно за [math]\displaystyle{ V }[/math] версий полная копия даёт [math]\displaystyle{ \Theta(Vn) }[/math], path copying — [math]\displaystyle{ O(V\log n) }[/math] для сбалансированного дерева. Точные классы зависят от модели (pointer machine) и структуры; [math]\displaystyle{ O(\log n) }[/math] в path copying достигается за счёт балансировки. См. рис. 6.

Трассировка примера

Проследим серию вставок в персистентное BST и число новых узлов на каждую операцию (прогон реализации из раздела «Служебное»).

Операция	Версия	Новых узлов	Общие поддеревья
старт	v0	0	—
insert(50)	v1	1	—
insert(30)	v2	2	—
insert(70)	v3	2	30
insert(20)	v4	3	70
insert(40)	v5	3	70, 20
insert(60)	v6	3	30, 20, 40
insert(80)	v7	3	30, 60
insert(55)	v8	4	30, 20, 40, 80

Вставка 55 в дерево из семи узлов создаёт четыре новых узла: путь 50 → 70 → 60 → 55 (копируются 50, 70, 60 и создаётся лист 55), тогда как полная копия дала бы семь. Все поддеревья вне пути (в частности, содержащие 20, 30, 40 и 80) разделяются между v7 и v8: это и есть sharing.

Проверка fat-узла: поле менялось в версиях 1, 4 и 7. Тогда Fat-Get(·, v) возвращает значение версии 1 при [math]\displaystyle{ v \in [1,3] }[/math], версии 4 при [math]\displaystyle{ v \in [4,6] }[/math] и версии 7 при [math]\displaystyle{ v \ge 7 }[/math] — поиск по истории даёт корректный «срез по времени».

Корректность и оценка сложности

Инвариант персистентности

Инвариант. Любая версия [math]\displaystyle{ v }[/math] остаётся корректной навсегда: её узлы и все достижимые из них узлы не изменяются после создания.

Для функциональных структур (path copying). Операция создаёт только новые узлы; поля старых узлов не присваиваются. Значит, множество узлов, достижимых из [math]\displaystyle{ v }[/math], и их поля постоянны — инвариант выполняется по определению.

Для fat nodes. Узлы «на месте» меняются, но каждое изменение фиксируется с номером версии; чтение на версии [math]\displaystyle{ v }[/math] выбирает последнее присваивание с номером [math]\displaystyle{ \le v }[/math]. Если все запросы версии [math]\displaystyle{ v }[/math] используют один и тот же номер [math]\displaystyle{ v }[/math], старое «содержимое» восстанавливается однозначно — инвариант сохраняется на уровне запроса.

Корректность path copying

Утверждение. Insert(v, k) возвращает корректное BST, содержащее тот же набор ключей, что и [math]\displaystyle{ v }[/math], плюс [math]\displaystyle{ k }[/math] (если его не было).

Доказательство (по индукции по высоте). База: пустое дерево → узел-лист с ключом [math]\displaystyle{ k }[/math], корректно. Шаг: при [math]\displaystyle{ k \lt v.\text{key} }[/math] рекурсивно вставляем в левое поддерево; по индукции получаем корректное BST [math]\displaystyle{ l' }[/math] с прежними ключами плюс [math]\displaystyle{ k }[/math]. Новый узел [math]\displaystyle{ \langle v.\text{key}, l', v.\text{right} \rangle }[/math] сохраняет порядок (все ключи [math]\displaystyle{ l' }[/math] меньше [math]\displaystyle{ v.\text{key} }[/math], все ключи [math]\displaystyle{ v.\text{right} }[/math] больше). Аналогично для правого поддерева. Ключ [math]\displaystyle{ k }[/math] не создаёт копий, если уже есть. [math]\displaystyle{ \square }[/math]

Оценка сложности и памяти

• Path copying. Время и число новых узлов — длина пути [math]\displaystyle{ O(h) }[/math]. Для сбалансированного дерева [math]\displaystyle{ h = O(\log n) }[/math]; для вырожденного — [math]\displaystyle{ O(n) }[/math]. Суммарно за [math]\displaystyle{ n }[/math] вставок — [math]\displaystyle{ O(n\log n) }[/math] узлов.
• Fat nodes. Обновление [math]\displaystyle{ O(1) }[/math] (добавление в список), доступ [math]\displaystyle{ O(\log m) }[/math] (двоичный поиск по истории длины [math]\displaystyle{ m }[/math]), память [math]\displaystyle{ O(1) }[/math] на изменение.
• Node copying. При ограниченной входящей степени — [math]\displaystyle{ O(1) }[/math] амортизированно на обновление и [math]\displaystyle{ O(1) }[/math] доступ; без ограничения метод теряет оценку.

Почему нельзя слепо копировать амортизацию

Оценки вида «амортизированно [math]\displaystyle{ O(1) }[/math]» опираются на последовательность операций. В персистентной структуре одну и ту же операцию можно выполнить из разных версий, поэтому делить работу на «число операций» нельзя: дорогой шаг «переигрывается» через ветвление. Именно поэтому, например, энергичная очередь на двух стеках (персистентная очередь) не даёт худшего [math]\displaystyle{ O(1) }[/math] без дополнительных приёмов (ленивые потоки и кредит/потенциал). Более того, для функциональных структур с ленью амортизацию удаётся сохранить, только если «долг» хранится внутри структуры (кредит у банкирской очереди, потенциал у физической) [3][4].

Сравнение с альтернативами

Метод	Обновление	Доступ к значению	Память на операцию	Когда выбирать
Полная копия	[math]\displaystyle{ \Theta(n) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ \Theta(n) }[/math]	крошечные структуры, простота
Path copying	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	сбалансированные деревья; функциональный стиль
Fat nodes	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(\log m) }[/math]	[math]\displaystyle{ O(1) }[/math]	важна память, дорогой доступ приемлем
Node copying	[math]\displaystyle{ O(1) }[/math] аморт.	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math] аморт.	ограниченная входящая степень
Функциональная пересборка	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(n) }[/math]	пакетные обновления, простота кода

Рис. 6. Ориентировочные оценки методов; точные классы зависят от модели и структуры.

Вердикт. Для деревьев почти всегда берут path copying: он прост и даёт [math]\displaystyle{ O(\log n) }[/math]. Когда память критична и структура произвольная, смотрят на fat nodes/node copying (с оговоркой про входящую степень). Если обновления пакетные — допустима пересборка. Для гарантии [math]\displaystyle{ O(1) }[/math] в худшем случае нужны специальные конструкции (очередь на шести стеках ).

Где применяется

1. Функциональные языки. В Haskell, OCaml, Standard ML списки, деревья и очереди неизменяемы; любая операция возвращает новое значение, а старые продолжают существовать. Почему: язык не допускает мутации, и персистентность — не надстройка, а базовый способ работы [3].
2. Системы контроля версий. Git хранит коммиты как DAG неизменяемых объектов (blob, tree, commit): новая версия ссылается на старые. Ветвление и слияние коммитов — операции над DAG, но это не confluent merge структур. Почему: неизменяемость даёт целостность и дешёвое ветвление [6].
3. СУБД и многоверсионность (MVCC). Читателю выдаётся снапшот, соответствующий версии данных на момент старта транзакции, а писатель не блокирует его. Индексы могут использовать versioned pages или copy-on-write; конкретный механизм зависит от СУБД. Почему: согласованное чтение без блокировок [4][7].
4. Вычислительная геометрия. Для точек, отрезков и планарных подразбиений методы персистентности позволяют отвечать на запросы «на момент времени [math]\displaystyle{ t }[/math]»; классическая работа Дрисколла и др. посвящена именно таким применениям [1].
5. Undo/redo и редакторы. История действий — дерево версий документа; откат — переход по ссылке, а не восстановление из журнала. Почему: [math]\displaystyle{ O(1) }[/math] для списка/стека и [math]\displaystyle{ O(\log n) }[/math] для дерева на шаг истории.
6. Параллельные вычисления. Неизменяемые данные безопасно разделяются между потоками без блокировок: гонки и порча общего состояния невозможны. Почему: нет записи в общие узлы.

См. рис. 7: общий мотив применений.

Рис. 7. Общий мотив: заменить мутацию созданием версии.

Историческая справка

Методы персистентности систематически изложили Джеймс Дрисколл, Нил Сарнак, Дэниел Слитор и Роберт Тарьян в работе Making Data Structures Persistent (STOC 1986; журнальная версия — Journal of Computer and System Sciences, 1989). Они ввели fat nodes и node copying и показали, что структуры с ограниченной входящей степенью можно сделать полностью персистентными за [math]\displaystyle{ O(1) }[/math] амортизированного времени и памяти на операцию [1]. Метод path copying для функциональных («аппликативных») структур описал Юджин Майерс (E. W. Myers) в работе Efficient Applicative Data Types (POPL 1984) ⚠️ требует проверки точных выходных данных [2].

Понятие функциональной персистентности и обширную коллекцию персистентных структур систематизировал Крис Окасаки в книге Purely Functional Data Structures (Cambridge University Press, 1998); он же показал, как сохранять амортизированные оценки в ленивых структурах (кредит/потенциал) [3]. Формальный амортизированный анализ, включая метод потенциала, развил Роберт Тарьян («Amortized Computational Complexity», 1985) [5]. Предшественником функциональных структур считаются списки LISP (Джон Маккарти, 1960).

Термин «персистентная структура данных» закрепился после работы [1]; обзоры и уточнения (ретроактивность, кинетические структуры) даны, например, в Handbook of Data Structures and Applications (глава H. Kaplan о персистентности) ⚠️ требует проверки деталей [8].

Типичные ошибки и подводные камни

• Копировать всё «на всякий случай». Новички копируют структуру целиком, получая [math]\displaystyle{ \Theta(n) }[/math] на операцию; выигрыш персистентности — именно в разделении.
• Мутировать разделяемые узлы. Любая запись в общий узел портит все версии, которые на него ссылаются; функциональный подход требует неизменяемости.
• Забыть про ограничение входящей степени. Node copying корректен и быстр только при [math]\displaystyle{ O(1) }[/math] входящих ссылок на узел; иначе число копий растёт.
• Ожидать [math]\displaystyle{ O(1) }[/math] доступа от fat nodes. Доступ — поиск по истории, обычно [math]\displaystyle{ O(\log m) }[/math]; путать дешёвое обновление с дешёвым чтением нельзя.
• Переносить амортизацию на персистентность без оговорок. Дорогая операция «переигрывается» через ветвление; нужен кредит/потенциал внутри структуры.
• Не освобождать недостижимые версии. Память растёт неограниченно; для удаления нужна сборка мусора (или явное «забывание» старых версий).
• Путать персистентность с транзакциями. Персистентность — про версии, а не про атомарность и изоляцию; это разные уровни абстракции.
• Сливать версии без правил (confluent). Merge должен быть определён и согласован с операциями структуры; коммутативность не обязательна — конкатенация списков не коммутативна.
• Считать path copying бесплатным для любой структуры. Он опирается на дерево и короткий путь; для графа с большим числом обратных ссылок он деградирует.
• Забывать про вырождение. В несбалансированном дереве path copying стоит [math]\displaystyle{ O(n) }[/math]; балансировка критична для оценки [math]\displaystyle{ O(\log n) }[/math].

Задачи для практики

1. Path copying. Реализуйте персистентное BST с insert через копирование пути. Ограничение: старые версии неизменяемы. Подсказка: возвращайте новый корень; не меняйте поля старых узлов.
2. Счёт узлов. Для вставки в сбалансированное дерево докажите, что создаётся [math]\displaystyle{ O(\log n) }[/math] узлов. Подсказка: копируется ровно путь.
3. Fat nodes. Реализуйте поле с историей (version, value) и чтение на версии [math]\displaystyle{ v }[/math] двоичным поиском. Оцените время Set/Get. Подсказка: upper_bound по номеру версии.
4. Ветвление. От версии [math]\displaystyle{ v }[/math] примените две разные вставки и покажите, что обе новые версии корректны и не влияют друг на друга. Подсказка: подумайте про дерево версий.
5. Память. Сравните суммарную память [math]\displaystyle{ n }[/math] обновлений при (а) полной копии и (б) path copying. Приведите асимптотики и численный пример при [math]\displaystyle{ n = 10^4 }[/math]. Подсказка: [math]\displaystyle{ \Theta(n^2) }[/math] против [math]\displaystyle{ O(n\log n) }[/math].
6. Node copying. Объясните, почему ограничение входящей степени необходимо, и приведите структуру, где оно нарушается. Подсказка: узел с [math]\displaystyle{ n }[/math] входящими ссылками.
7. Амортизация. Приведите пример, где амортизированная граница ломается при ветвлении, и объясните, как кредит/потенциал это исправляет. Подсказка: см. Персистентная очередь.
8. Confluent. Предложите правило merge для персистентного множества ключей (объединение без дубликатов) и оцените время. Подсказка: слияние двух деревьев поиска.

Связанные темы

• Персистентный стек — простейшая персистентная структура (список и массив запросов).
• Персистентная очередь — персистентность очереди, ленивые очереди Окасаки.
• Очередь на шести стеках — [math]\displaystyle{ O(1) }[/math] в худшем случае; персистентная очередь на пяти стеках.
• Декартово дерево — персистентный treap (split/merge, path copying).
• Двоичное дерево поиска — база для path copying.
• B+-дерево — индекс СУБД; обновление копированием пути.
• Асимптотическая сложность — амортизация, метод потенциала, худший случай.

Источники

1. Driscoll J. R., Sarnak N., Sleator D. D., Tarjan R. E. Making Data Structures Persistent // STOC 1986; Journal of Computer and System Sciences. — 1989. — Vol. 38 (fat nodes, node copying, ограниченная входящая степень).
2. Myers E. W. Efficient Applicative Data Types // POPL. — 1984 (path copying для аппликативных структур) ⚠️ требует проверки точных выходных данных.
3. Okasaki C. Purely Functional Data Structures. — Cambridge University Press, 1998.
4. Silberschatz A., Korth H. F., Sudarshan S. Database System Concepts. — McGraw-Hill, 7th ed., 2019 (многоверсионность, индексы).
5. Tarjan R. E. Amortized Computational Complexity // SIAM J. Algebraic and Discrete Methods. — 1985. — Vol. 6, № 2.
6. Chacon S., Straub B. Pro Git. — Apress, 2nd ed., 2014 (объекты и DAG версий).
7. Wikipedia: Persistent data structure. URL: https://en.wikipedia.org/wiki/Persistent_data_structure.
8. Kaplan H. Persistent Data Structures // Handbook of Data Structures and Applications. — Chapman & Hall/CRC, 2004.