142
правки
Изменения
→Метод «толстых» узлов
===Метод «толстых» узлов===
Пусть в структуре данных есть узел, в котором нужно сделать изменения (например, на нашем рисунке ниже в первой версии структуры данных есть поле <tex>a=3</tex>, а во второй версии это поле должно быть равно <tex>4</tex>), но при этом нужно сохранить доступ к старой версии узла и не нужно экономить время. В таком случае можно хранить их оба в большом комбинированном узле.
[[Файл:Метод толстых узлов.png|600px|центр]]
В примере выше в этом «толстом» узле будет храниться первая версия <tex>V_1</tex>, у которой <tex>a=3</tex> и вторая версия <tex>V_2</tex>, у которой <tex>a=4</tex>. Если далее последуют еще какие-то изменения (например, поле <tex>b</tex> нашего узла станет равно <tex>5</tex>) сделаем еще одну версию структуры данных — <tex>V_3</tex>.
[[Файл:Список версий1.png|500px|центр]]
Пусть нужно сделать запрос ко второй версии структуры данных (на рисунке выше это запрос <tex>X.a-?)</tex>. Чтобы сделать этот запрос нужно зайти в узел <tex>X</tex> и найти в списке версий максимальную версию, которая меньше или равна версии запроса (в примере на рисунке это версия <tex>2</tex>), и в этой версии узла найти значение поля <tex>a</tex> (в примере <tex>a=4</tex>).
