维护森林连通性——动态树

动态树的基本操作： 维护森林连通性——动态树 华东师大二附中 陈首元 本文将介绍一种数据结构，称为动态树，它能够维护一个带权的森林，并支持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; 通过上面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步操作的时间复杂度 为： 定义s(i)为在动态树中以i为根子树中的节点数。定义r(i)为log2(s(x))。定义一棵动态树的势为这棵动态树中所有节点的r(i)和。 伸展树有一个的性质：每一次splay操作的均摊复杂度不超过：3(r(t)-r(x))+1（t为这棵伸展树的树根），而这个性质用在这个问题里也是正确的（在r(i)的定义改变之后）。下面简单地证明如下。 证明：用r’(x)表示操作以后的顶点x，r(x)表示操作以前的顶点x。 1.​ 单旋转 1+r’(x)+r’(y)-r(x)-r(y) <=1+r’(x)-r(x) (r(y)>=r’(y)) <=1+3*(r’(x)-r(x)) (r’(x)>=r(x)) 2.​ 双旋转（顶点x不是根，且顶点x与x的父节点使他们父节点的左儿子） 2+r’(x)+r’(y)+r’(z)-r(x)-r(y)-r(z) =2+r’(y)+r’(z)-r(x)-r(y) (r’(x)=r(z)) <=2+r’(x)+r’(z)-2r(x) (r’(x)>=r’(y))and(r(y)>=r(x)) 由对数函数的性质，对于任意一对x,y>0 x+y<=1，满足log(x)+log(y)<=-2。 r(x)+r’(z)-2r’(x)=log(s(x)/s’(x))+log(s’(z)/s’(x))<=-2 即2r’(x)-r(x)-r’(z)>=2 由此可得3(r’(x)-r(x))-(2+r’(x)+r’(z)-2r(x))=2r’(x)-r(x)-r’(z)-2>=0 3.​ 另一种情况的双旋转，分析与前一种情况类似，省略。 Splay操作是通过多次旋转，将这些旋转的复杂度叠加就得到最多3(r(t)-r(x))+1，于是得证。 Expose(v)操作把从v到动态树树根的路径上的所有虚边消除，并合并路径上的伸展树，由前面的结论，路径的合并操作均摊复杂度不超过3*(r(tail)-r(head))+1，叠加后可得到expose(v)复杂度不超过3(r(root)-r(v))+k，(k是从v到树根路径上虚边个数)，由前面的结论(1)，可知平均k是对数级别的，而r(root)-r(v)也是对数级别的，所以Expose(v)均摊复杂度为O(logN)。这也是所有动态树操作的时间界。 Link-cut操作会改变动态树的势，但仍然是对数级别的。 [应用] 1、​ 最近公共祖先 询问v,w的最近公共祖先，首先执行expose(v)，再执行expose(w)，当执行expose(w)时，记录最近的一个再上次expose中被访问的点，这个点就是最近公共祖先。 每次询问需要O(logN)时间。 2、​ 集合的合并与分离 可以支持Union和Find操作，还能支持以某种方式分离，而每个集合操作的时间复杂度为O(logN) 3、​ 最大流 动态树可以用来优化最短路径增广算法，使每次增广的复杂度降为O(mlogN)，并使总复杂度为O(mnlogN)。 4、​ 最小生成树 动态树在最小生成树问题中有许多应用。 比如，最小生成树的增量算法、度限制生成树。还有其他许多种变形。 [实现] 直接使用前面的算法，空间复杂度会比较高，下面介绍一种本质相同的算法，空间复杂度会降低。而且编程也略微简单一些。 同样的，并不保存整棵树，而保存“虚拟树”。虚拟树中的顶点与动态树中的是一一对应的。虚拟树中的每个顶点最多连出两条实边，其余为虚边，分别成为左儿子和右儿子，其他顶点称为中间顶点。完全由实边组成的子树称为实树。对每个顶点记录它的父节点p(x)，左儿子和右儿子left(x)，right(x)。记每个顶点的费用为cost(x)，其子树中最小费用为mincost(x)。为了实现reverse，对每个节点保存一个reverse的标志。为了实现update函数，每个节点保存dcost,dmin两个量： 如果x是一颗实树的根：dcost(x)=cost(x) 否则dcost(x)=cost(x)-cost(p(x)) dmin(x)=cost(x)-mincost(x) 注意dmin是非负的。 实现expose需要两种操作：一种是splay，将一棵实树（也是二叉树），从某个节点伸展使这个节点成为这个实树的根。第二种是splice，将某个节点的一个中间节点变为左儿子，左儿子变为中间节点。 执行expose(v)操作需要分为三步。首先沿v往上到虚拟树的树根，对沿路的各实树进行splay，执行完这个步后从v到树根的路径上只有虚边。再沿v往上到虚拟树的树根，对沿路各节点执行splice，将从v到虚拟树树根路径上的边变为虚边。这时v和树根在一个实树中了。这时再执行splay(v)，把v调整为树根。 有了expose(v)，动态树的8个功能就可以实现了。 可以看出，这个算法和原算法的本质是相同的，所以它们的复杂度也是一样的。即均摊每步O(logN)。下面简单说说splay操作时dcost和dmin的维护。 对于splay，假设需要旋转的边连接节点v与节点v的父节点w，令a,b为旋转前v的左右儿子。b,c为旋转后w的左右儿子。dcost与dmin的变化如下： dcost’(v)=dcost(v)+dcost(w) dcost’(w)=-dcost(v) dcost’(b)=dcost(v)+dcost(b) dmin’(w)=max(0,dmin(b)-dcost’(b),dmin(c)-dcost(c)) dmin’(v)=max(0,dmin(a)-dcost(a),dmin’(w)-dcost’(w)) 其他节点的量不变。 对于splice，假设v是w的新的左儿子，w原来的左儿子为u dcost’(v)=dcost(v)-dcost(w) dcost’(u)=dcost(u)+dcost(w) dmin’(w)=max(0,dmin(v)-dcost’(v),dmin(right(v))-dcost(right(v))) 其他节点的量不变。 [参考文献] [1] Sleator and Tarjan A data structure for dynamic trees. [2] Sleator and Tarjan Self adjusting binary search tree. [3] Georgiads, Tarjan, Werneck Design of Data Structure for Mergeable Trees. [4] 拉文德拉 K.阿胡亚 托马斯L.马南提 詹姆斯 B.沃林 网络流理论、算法与应用 机械工业出版社