142
правки
Изменения
→Получение полностью персистентных структур данных
[[Файл:Полная персистентность.png]]
Для реализации описанного в предыдущем пункте метода преобразования структур данных в полностью персистентные нам нужен такой список, который поддерживает операции ''«insert after»'' и ''«order»''. Обе операции нужно делать за <tex>O(1</tex>). Это список с поддержкой запроса о порядке (''[[ http://www.cs.au.dk/~gerth/aa11/slides/order.pdf| List Order Maintenance'')]].
Операция обновления в этом списке будет происходить так: в список версий добавляется два элемента – первый вносит изменение, а второй будет возвращать обратно значение предыдущей версии. Таким образом, каждая операция разбивается на две: первая делает изменение, а вторая его откатывает.
В ''change log'' «толстого» узла теперь будем добавлять два события: одно указывает на изменение, произошедшее в соответствующей версии, а другое на его отмену. События будут отсортированы по их порядку в списке версий с помощью ''List Order Maintenance''.
