142
правки
Изменения
→Метод «толстых» узлов
Чтобы быстро найти нужную версию в списке версий, хранящихся в «толстом» узле, нужно хранить их в виде дерева. Тогда мы сможем за логарифм найти нужную версию и к ней обратиться. Значит все операции, которые будут производиться на этой структуре данных, будут домножаться на логарифм от числа версий.
Структура толстого узла может быть и другой: к каждой вершине можно хранить лог ее изменений, в который записывается версия, в которой произошло изменение, а также само изменение. Такая структура толстого узла рассмотрена ниже, в разделах об общих методах получения частично и полностью персистентных структур данных. Лог может быть организован по-разному. Обычно делают отдельный лог для каждого поля этой вершины. Когда что-то меняется в вершине, то в лог соответствующего поля записывается это изменение и номер версии, с которой данное изменение произошло. Когда нужно обратиться к старой версии, то двоичным поиском ищут в логе последнее изменение до этой версии и находят нужное значение.
Метод ''fat node'' дает замедление <tex> \log t</tex>, где <tex>t</tex> — число изменений структуры данных; памяти требуется <tex>n+t</tex>, где <tex>n</tex> — число вершин в структуре данных.
