234
правки
Изменения
→Решение задачи в частном случае
==Решение задачи в частном случае==
Сначала научимся выполнять эти операции для частного случая, в котором все деревья - это пути. Для этого представим путь в виде splay-дерева, в котором ключи выбираются равными глубине вершины. [[Файл:Path_to_tree.png|250px|thumb|right|Пример построения дерева для пути]]
Тогда операциям <tex>link </tex> и <tex>cut </tex> будут соответствовать <tex>merge </tex> и <tex>split</tex>.
Чтобы прибавлять заданное число на пути от вершины до корня, будем в каждой вершине хранить величину <tex>\Delta w</tex>, которая равна разнице между весом вершины и весом её родителя. Для корня это значение равно весу самого корня. Поэтому вес вершины определятся следующим образом:
