维护森林连通性——动态树
华东师大二附中
陈首元
本文将介绍一种数据结构，称为动态树，它能够维护一个带权的森林，并支持link操作，用途是将两棵树合并。支持cut操作，用途是删除一条边，是一棵树分为两棵。在网络优化中的用途十分广泛。
[动态树的基本操作]
Parent(v)： 返回v的父亲节点，如果是根返回null。 Root(v)：返回包含节点v的树的根。
Cost(v)：返回边（v,parent(v)）的费用，假定v不是根。 Mincost(v)：返回从root(v)到v的路径上权最小的边。 Update(v,x:real)：使从root(v)到v路径上的边的费用+x。 Link(v,w,x:real)：将以v为根的树连接到节点w上，（v,w）的费用为x。 Cut(v)：从树中删除(v,parent(v))，分为两棵树。
Evert(v)：翻转，将v设为根，并将v到root(v)上所有边反向。
1、 通过两次update可以修改一条边的费用。 2、 Mincost可以改为Maxcost
假设初始情况下有n个单独的点，接下来要执行m步上述的操作。
显然，通过保存dparent(v)，dcost(v)，分别记录v的父节点，与边的费用，可以实现朴素算法，在O(1)实现parent,cost,link,cut而root,mincost,evert,update的复杂度与树的深度有关，最坏情况下是O(n)。
本文的算法，并不直接对整棵树进行操作，通过这种算法，m步操作可以在O(mlogN)内实现。
将树中的边分成实边虚边两种，从每个顶点出发，最多有1条实边连向它的子节点。一个路径包括一些自底向上连通的实边。剩下的边都是虚边，通过记录dparent(v),dcost(v)，可以将所有的虚边都保存下来，虚边可以在一定条件下转化为实边并保存。如果tail(P)是树根，那么dparent(P)=null。
通过对完全由实边组成的路径进行操作，就能够实现动态树操作了。这里假定已经实现了以下的一些路径操作，先说明这些路径操作的功能，再介绍如何通过这些路径操作实现前面所说的基本操作，最后再讨论实现这些路径操作的方法。
[路径结构的基本操作]
Path(v)：返回包含v的路径 （每个路径有一个标志） Head(p)：返回路径p的首节点 Tail(p)：返回路径p的尾节点
Before(v)：返回路径中v的前驱节点
After(v)：返回路径中v的后继节点 Pcost(v)：返回边(v,after(v))的费用 Pmincost(p)：返回p中费用最小的边
Pupdate(p,x:real)：将p中每条边的费用+x Reverse(p)：将p中的每条边反向
Concatenate(p,q,x:real)：添加边（tail(p),head(q)）费用为x，将路径p,q合并 Split(v)：通过删除与v相连的边，将路径path(v)分为三部分，返回p,q,x,y，
p是head(path(v))到before(v),q是after(v)到tail(path(v))。 x是（before(v),v）的费用，y是(v,after(v))的费用。
如果v是头节点，那么p是null，如果v是尾节点那么q是null。
通过下面两种操作，我们就能维护树中的实边虚边，并实现动态树的基本操作。 Splice(p:path)：作用是将路径p向更靠近根的方向增长。
实现方法：把虚边(tail(P),dParent(p)) 变为实边，为了维护实边的性质，将原来从dParent(P)中连出的边设为虚边。 下面是伪代码
Function splice(p:Path); Begin
U:=dparent(tail(P)); [q,r,x,y]:=split(u); If q<>nil Then Begin
dparent(tail(q)):=v; dcost(tail(q)):=x; End;
P:=concatenate(p,path(P),dcost(tail(P)); If r=nil Then return p
Else return concatenate(p,r,y); End;
Expose(v:vertex)：作用是将从v到root(v)中所有边设为实边。 实现方法：不断调用splice直到根为止。 Fucntion expose(v:vertex); Begin
[q,r,x,y]:=split(v); If q<>nil Then Begin
Dparent(tail(q)):=v; Dcost(tail(q)):=x; End;
If r=nil Then p:=path(V)
Else p:=concatenate(path(V),r,y);
While dparent(v)<>nil do p:=splice(p); Return p; End;
splice
expose
通过上面2个操作，和路径的基本操作，我们就能把8个动态树基本操作实现了。 Function Parent(v:vertex) Begin
If v=tail(path(v)) Then Return Dparent(v) Else Return after(v) End;
Function cost(v:vertex) Begin
If v=tail(path(v)) Return dcost(v) Else Return Pcost(v) End;
Function root(v:vertex); Begin
Return tail(expose(v)); End;
Function Mincost(v:vertex);
Begin
Return Pmincost(expose(v)); End;
Procedure Update(v:vertex;x:real); Begin
Pupdate(expose(v),x); End;
Procedure Link(v,w:vertex;x:real); Begin
Concatenate(path(v),expose(w),x); End;
Function Cut(v:vertex); Var
p,q:path; x,y:real; Begin
Expose(v);
[p,q,x,y]:=split(v); Dparent(v):=nil; Return y; End;
Procedure Evert(v); Begin
Reverse(expose(v)); Dparent(v):=nil; End;
至此，我们已把树的问题转化为链的问题了。下面介绍如何实现这些路径操作。
[路径结构的实现]
可以用伸展树存放路径，路径上的点以它们离头节点的距离大小为权值组成伸展树。 reverse操作：
对每个节点保存reverse标志，如果为真，表示以这个节点为根的子树是需要翻转的，即对这棵子树的每个子节点的左右儿子互换。在访问一个节点ｖ的时候，如果reverse标志为真那么交换左右子节点，并将reverse标志设为假，再把reverse标志传递到子节点（取反） 执行reverse操作时只需改变根节点的reverse值 pupdate操作：
对每个子节点v保存2个量，ecost，change。cost表示(v,after(v))的权值，change代表了以v为根的子树中边权值的修正量。在访问一个节点ｖ的时候，令ecost=ecost+change，
再将change设为0，最后让change值传递到子节点（加到子节点的change值上） 另外对每个节点都保存emin，表示以此节点为根的子树中的最小权值。 执行update操作时只需修改根节点的change值
Path(v)：先沿父指针向上找到根节点并返回，然后沿此路径向下并维护reverse,change,ecost等值
Tail(p)：返回最右子孙 Head(p)：返回最左子孙
Before,After与伸展树中的操作一样
（path,tail,head的时间复杂度与splay(v)相同，不会影响以后的分析） Concatenate(p,q,x)：令r=tail(p) 首先splay(r)，再令path(q)作为r的右儿子，访问head(path(q))，并修改它的ecost值为x。最后修改r的emin值，使它符合定义。
Split(v)：首先splay(v)，维护change，reverse的值，删掉与其相联的两条边（如果没有返回null），返回值为：[v的左儿子，v的右儿子，tail(v左儿子)的ecost，head(v右儿子)的ecost。（伸展树操作：Splay(v)，树通过旋转将ｖ节点调整至树根，旋转时维护emin） 在每次split和concatenate操作之后，splay最左子孙，使它成为根。
[复杂度分析]
1. 每一个动态树操作都需要用到1次expose()，首先分析expose()的次数。
对于边v->w（动态树中，不是伸展树中），如果v的子孙〉w的子孙/2，称为A类边，否则成为B类边。
显然每个点最多连出一条Ａ类边，树中每条路径上最多有O(log2N)条Ｂ类边。 令p为B类边中的虚边数。
执行一次expose，可能执行许多splice操作，每一次splice操作： 添加一条B类虚边进入路径：p+1
这种情况最多发生O(log2N)次 添加一条A类虚边进入路径：p-1
可能发生许多次，但代价是p，p是保持非负的。
由上面分析可以看出平均每次expose操作要执行O(log2N)次路径操作。（1）
2. 每次splay的均摊操作复杂度是O(logN)，一个简单的结果是每次动态树操作O(log2N)。
（如果使用AVL，红黑树等平衡二叉树来实现路径结构的话复杂度就是O(log2N)，但伸展树的均摊复杂度比这个结果少了logN） 下面更进一步分析均摊时间复杂度。 先介绍一下均摊复杂度的定义：
对整棵伸展树定义一个势p，一个操作的均摊复杂度a=t+p’-p，其中t为实际操作
时间p为操作前的势，p’为操作之后的势。那么m步操作的时间复杂度
?t(i)为：
i?1i?1i?1
定义s(i)为在动态树中以i为根子树中的节点数。定义r(i)为log2(s(x))。定义一棵动态树的势为这棵动态树中所有节点的r(i)和。
伸展树有一个的性质：每一次splay操作的均摊复杂度不超过：3(r(t)-r(x))+1（t为这棵
?t(i)??(ai?pi?1?pi)??ai?p0?pmmmm
大学课件--维护森林连通性——动态树-
