Изменения

Пусть мы храним историю изменения версий в виде дерева. Сделаем[[Обход в глубину, цвета вершин| обход этого дерева в глубину]]. В порядке этого обхода запишем, когда мы входим, а когда выходим из каждой версии. Эта последовательность действий полностью задает дерево, сделаем из нее список. Когда после какой-то версии (на рисунке ниже это версия <tex>6</tex>) добавляется новая версия нашей структуры данных(на рисунке версия <tex>8</tex>), мы вставляем два элемента в середину спискасписок (на рисунке это <tex>8</tex> и <tex>-8</tex>) после той версии, когда пришло изменение. Первый элемент вносит изменение, а второй будет возвращать обратно значение предыдущей версии. Таким образом, каждая операция разбивается на две: первая делает изменение, а вторая его откатывает.

Для реализации описанного в предыдущем пункте метода преобразования структур данных в полностью персистентные нам нужен такой список, который поддерживает операции ''«insert after»'' <tex> insert After(p,q)</tex> (вставить <tex>q</tex> после <tex>p</tex>) и <tex>order(p,q)</tex> (должен уметь ответить верно ли что <tex>p</tex> лежит в этом списке до <tex>q</tex>). <tex>Order(p,q)</tex> возвращает <tex>1</tex>, если <tex>p</tex> лежит до <tex>q</tex> и ''«order»''<tex>0</tex> иначе. Обе операции нужно делать за <tex>O(1)</tex>. Это список с поддержкой запроса о порядке ''List Order Maintenance'' <ref>[http://www.cs.au.dk/~gerth/aa11/slides/order.pdf{{---}} List Order Maintenance]</ref>.Операция обновления в этом списке будет происходить так: в список версий добавляется два элемента — первый вносит изменение, а второй будет возвращать обратно значение предыдущей версии. Таким образом, каждая операция разбивается на две: первая делает изменение, а вторая его откатывает.В ''change log'' «толстого» узла теперь будем добавлять два события: одно указывает на изменение, произошедшее в соответствующей версии, а другое на его отмену. События будут добавляться в ''change log'' по их порядку в списке версий ''List Order Maintenance''.  Когда есть запрос к какой-то версии нужно найти в списке версий такую, после входа в которую, но до выхода из которой лежит версия запроса, а среди таких максимальную.