算法合集之维护森林连通性——动态树.pptx

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