算法合集之《维护森林连通性-动态树》.ppt

维护森林连通性动态树,华东师大二附中 陈首元,动态树,维护一个森林支持边的插入与删除支持树的合并与分离支持寻找路径上费用最小的边所有操作的均摊复杂度为O(logN),2,3,4,5,6,7,8,1,10,20,-20,0,30,-5,-5,Root(1,2,3,4,5,6,7,8)=1MinCost(6)=10,Update(7,10),5,40,Evert(6),新树根,Cut(4),Root(7,8)=4,Link(3,4,10),动态树的基本操作,Root(v)返回包含节点v的树的根MinCost(v)返回v到根路径上费用最小的边Update(v,x)使v到树根路径上的边的费用+x Link(v,w,x)将以v为根的树连接到节点root(w)上，（v,w）的费用为x Cut(v)删除v与其父节点连接的边Evert(v)使v成为新的根，并将v到原树根上的边反向,操作的实现,将树中的边分为实边、虚边两种，每个节点最多向其子节点连出一条实边将树划分为一些完全由实边组成的路径，只对这些路径进行操作,一条路径,头,尾,路径的基本操作,Path(v)：返回包含v的路径（每个路径有一个标志）Head(p),Tail(p)：返回首节点、尾节点Pmincost(p)：返回p中费用最小的边Pupdate(p,x:real)：将p中每条边的费用+xReverse(p)：将p中的每条边反向Concatenate(p,q,x)：添加边(tail(p),head(q)）费用为x，将路径p,q合并 Split(v)：将v从路径中删除并把路径分为两部分,Splice,Splice(p)：将路径p向更靠近根的方向增长实现方法：把虚边(tail(P),Parent(p)变为实边，为了维护实边的性质，将原来从Parent(P)中连出的边设为虚边,Expose,Expose(v)：将从v到树根路径上的所有边设为实边 实现方法：不断调用splice直到根为止,有了Expose(v)，就可以实现所有动态树操作了,Link操作,Procedure Link(v,w:vertex;x:real);Begin Concatenate(path(v),expose(w),x);End;,Cut操作,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;,路径结构,用伸展树保存路径所有路径操作都能用Splay实现对于Reverse与PUpdate操作，可以采用先存放修改标志，在访问时修改的办法在每次Split和Concatenate操作之后，Splay最左子孙，使它成为根,复杂度分析(Expose分析),对于边v-w（动态树中，不是伸展树中）如果v的子孙w的子孙一半，称为A类边，否则成为B类边。显然每个点最多连出一条类边，树中每条路径上最多有O(logN)条B类边。令p为B类边中的虚边数。,复杂度分析(Expose分析),一次Expose操作，将执行数次Splice对于每次Splice：添加一条B类虚边进入路径：p+1这种情况最多发生O(logN)次添加一条A类虚边进入路径：p-1可能发生许多次，但代价是p，p是保持非负的。由上面分析可以看出平均每次expose操作要执行O(logN)次路径操作,复杂度分析(Splay分析),势函数定义r(x)：x在动态树中的子节点数的对数伸展树的性质：每一次splay操作的均摊复杂度不超过：3(r(t)-r(x)+1 此性质在势函数定义改变后依然成立,复杂度分析,Expose的均摊复杂度3(r(root)-r(v)+(v到树根路径上的节点数）由Expose分析得到路径上的节点数平均为O(logN)复杂度为O(logN),实现,不保存整棵树，而保存“虚拟树”。虚拟树中的顶点与动态树中的是一一对应的。虚拟树中的每个顶点最多连出两条实边，其余为虚边，分别成为左儿子和右儿子，其他顶点称为中间顶点。完全由实边组成的子树称为实树。,实现,实现expose需要两种操作：一种是splay，将一棵实树（也是二叉树），从某个节点伸展使这个节点成为这个实树的根。第二种是splice，将某个节点的一个中间节点变为左儿子，左儿子变为中间节点。执行expose(v)操作需要分为三步。首先沿v往上到虚拟树的树根，对沿路的各实树进行splay，执行完这个步后从v到树根的路径上只有虚边。再沿v往上到虚拟树的树根，对沿路各节点执行splice，将从v到虚拟树树根路径上的边变为虚边。这时v和树根在一个实树中了。这时再执行splay(v)，把v调整为树根。,谢谢,