3622
правки
Изменения
м
→Метод «толстых» узлов
Пусть нужно сделать запрос ко второй версии структуры данных (на рисунке выше это запрос <tex>X.a-?)</tex>. Чтобы сделать этот запрос, нужно зайти в узел <tex>X</tex> и найти в списке версий максимальную версию, которая меньше или равна версии запроса (в примере на рисунке это версия <tex>2</tex>), и в этой версии узла найти значение поля <tex>a</tex> (в примере <tex>a=4</tex>).
Чтобы быстро найти нужную версию в списке версий, хранящихся в «толстом» узле, нужно хранить их в виде дерева. Тогда мы сможем за логарифм найти нужную версию и к ней обратиться. Значит , все операции, которые будут производиться на этой структуре данных, будут домножаться на логарифм от числа версий.
Структура толстого узла может быть и другой: к каждой вершине можно хранить лог ее изменений, в который записывается версия, в которой произошло изменение, а также само изменение. Такая структура толстого узла рассмотрена ниже, в разделах об общих методах получения частично и полностью персистентных структур данных. Лог может быть организован по-разному. Обычно делают отдельный лог для каждого поля вершины. Когда что-то меняется в вершине, то в лог соответствующего поля записывается это изменение и номер версии, с которой данное изменение произошло. Когда нужно обратиться к старой версии, то двоичным поиском ищут в логе последнее изменение до этой версии и находят нужное значение.
