308
правок
Изменения
м
Нет описания правки
==Решение задачи в частном случае==
Сначала научимся выполнять эти операции для частного случая, в котором все деревья - это пути. Для этого представим путь в виде splay-дерева, в которм котором ключи выбираются равными глубине вершины. [[Файл:Path_to_tree.png|250px|thumb|right|Пример построения дерева для пути]]Тогда операциям link и cut будут соответсвовать соответствовать merge и split.
Чтобы прибавлять заданное число на пути от вершины до корня, будем в каждой вершине хранить велечину величину <tex>\Delta w</tex>, которая равна разнице между весом вершины и весом её родителя. Для корня это значение равно весу самого корня. Поэтому вес вершины определятся следующим образом:
сумма
При прибавлении <tex>\alpha</tex> на пути от вершины <tex>v</tex> до корня, сначала вызвается вызывается <tex>splay(v)</tex>, после чего в левом поддереве находятся вершины, которые лежат на пути к корню. Затем надо прибавить <tex>\alpha</tex> к <tex>\Delta w(v)</tex> и ,чтобы сохранить веса вершин, которые находятся ниже в пути, вычесть <tex>\alpha</tex> от <tex>\Delta w(v.right)</tex>.
[[Файл:Linkcut_weights.png|250px|thumb|right|]]
Для поиска минимума поступим аналогично. Определим <tex>\Delta min(v)</tex> таким образом, чтобы сохранялся следующий инвариант: <tex>min(v) = \Delta min(v) + w(v) </tex>. Пусть <tex>l</tex> и <tex>r</tex> дети <tex>v</tex>, тогда
<tex>min(v) = min\{w(v), \ min(l), \ min(r)\}</tex>
<tex>\Delta min(v) = min(v) - w(v) \\
= min\{w(v) - w(v), \ min(l) - w(v), \ min(r) - w(v)\} \\= min\{0, \ (\Delta min(l) + w(l)) - w(v), \ (\Delta min(r) + w(r)) - w(v)\} \\= min\{0, \ \Delta min(l) + \Delta w(l), \ \Delta min(r) + \Delta w(r)\}</tex>
Чтобы найти минимум на пути, надо вызвать <tex>splay(v)</tex>, а затем сравнить минимум <tex>v</tex> и минимум её левого ребенка.
==Link-cut tree==
Чтобы обобщить, разобъем разобьем дерево на множество непересекающихся путей. Каждое ребро обозначим либо solid-ребром, либо dashed-ребром. Все пути в представляемом дереве хранятся в виде splay-деревьев. Корень каждого splay-дерева хранит указатель на вершину-родителя.
[[Файл:Linkcut_paths.png|500px||center|Разбиение дерева на пути]]
parent(right(p)) <- null //поэтому правое поддерево p делаем новым путем
pathparent(right(p)) <- p
right(p) <- v //объеденяем объединяем оставшийся и построенный пути
Δw(v) -= Δw(p)
Δmin(p) = min{0, Δmin(left(p)) + Δw(left(p)), Δmin(right(p)) + Δw(right(p))}
===cut(v)===
Отрезает дерево с корнем <tex>v</tex>. После вызова <tex>expose(v)</tex> <tex>\ v</tex> станет корнем splay-дерева, и в правом поддереве будут содержатся все вершины, которые были ниже <tex>v</tex> в представляемом дереве, а в левом - те что выше. Обнулив указатель на левого ребенка <tex>v</tex> и на родителя в левом поддереве, получим требуемое.
cut(v)
==Оценка времени работы==
Назовем ребро из <tex>u</tex> в её родителя <tex>v</tex> тяжелым, если количество детей <tex>u</tex> <tex>d(u) > \frac{1/}{2 } d(v)</tex>.
Лемма. Каждая вершина имеет не более одного тяжелого ребра
M = |{все ребра, преобразованные из dashed в solid}| = |{легкие dashed-ребра, преобразованные в solid}| + |{тяжелые dashed-ребра, преобразованные в solid}|
По лемме, количество легких <tex>dashed</tex>-ребер, преобразованных в <tex>solid</tex>, будет не больше, чем <tex>\log(n)</tex>.
Обозначим за <tex>F</tex> лес деревьев, в которых каждое ребро либо solid, либо dashed, a <tex>F'</tex> - лес, получившийся из <tex>F</tex> после одного вызова <tex>expose</tex>. Определим потенциал <tex>\Phi _{a}(F) = n - 1 - |\{heavy solid-edges\}|</tex>. Пусть <tex>H</tex> - множество всех тяжелых ребер, <tex>L</tex> - все легкие ребра, <tex>S->\rightarrow D</tex> - множество solid-ребер, преобразованных в dashed в течение одного <tex>expose</tex>, <tex>D->\rightarrow S</tex> - множество dashed-ребер, преобразованных в solid, <tex>\Delta \Phi _{a}</tex> - увеличение <tex>\Phi _{a}</tex> после одной операции <tex>expose</tex>.
Лемма2. <tex>V = M + \Delta \Phi _{a}<= 1 + 2log(2\log n)</tex>
<tex>V = M + \Delta \Phi _{a}\\
= M + |H \cap S->\rightarrow D| - |H \cap D->\rightarrow S| \\\leqslant M + |L \cap D->\rightarrow S| - |H \cap D->\rightarrow S| \\= 2 * |L \cap D->\rightarrow S| \\=2 * \log(n)
</tex>
Теперь проанализируем <tex>M</tex>. Используя тот факт, что начальное значение <tex>\Phi _{a}</tex> не превосходит <tex>n - 1</tex>, приходим к тому, что для деревьев с <tex>n</tex> вершинами, по крайней мере за <tex>n - 1</tex> операцию <tex>expose</tex>, среднее <tex>M</tex> на одну операцию будет не больше, чем <tex>1 + 2log(2\log n)</tex>
Докажем, что амортизационная стоимость операции изменения класса ребер в link-cut-дереве равна <tex>O(1)</tex>
Пусть </tex>s(v)</tex> - количество вершин в поддеревьях <tex>v</tex>(здесь имеется в виду splay-дерево T пути, котоый строится в ходе выполнения <tex>expose</tex>). <tex>\Phi = \sum_{v} \log(s(v))</tex>. Нам известно, что стоимость i-той операции splay не превосходит 1 + 3*(r'(v_{i} - r(v_{i})). После каждого <tex>splay(v)</tex> v соединена с w = pathparent(v), поэтому s(w) > s(v). Это приводит к тому, что амортизационная стоимость <tex>expose</tex> ограничена следующим значением
<tex>3 * \log(n) - 3*\log(s(v)) + M</tex>
Здесь <tex>M = O(\log(n))</tex>, поэтому амортизационная стоимость <tex>expose</tex> равна <tex>O(\log(n))</tex>
