Изменения

Перейти к: навигация, поиск

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

Нет изменений в размере, 08:16, 20 апреля 2015
Получение полностью персистентных структур данных
[[Файл:Полная персистентность.png‎]]
Для реализации описанного в предыдущем пункте метода преобразования структур данных в полностью персистентные нам нужен такой список, который поддерживает операции <tex> insert After(p,q)</tex> (вставить <tex>q</tex> после <tex>p</tex>) и <tex>order(p,q)</tex> (должен уметь ответить верно ли что <tex>p</tex> лежит в этом списке до <tex>q</tex>). <tex>Orderorder(p,q)</tex> возвращает <tex>1</tex>, если <tex>p</tex> лежит до <tex>q</tex> и <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''.
Анонимный участник

Навигация