Изменения

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