5-finding the depth

5-finding the depth

ID:18592901

大小:81.00 KB

页数:8页

时间:2018-09-19

5-finding the depth_第1页
5-finding the depth_第2页
5-finding the depth_第3页
5-finding the depth_第4页
5-finding the depth_第5页
资源描述:

《5-finding the depth》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、确定深度问题考虑2类指令Link(v,r):v是一棵树中的结点,r是另一棵树的根,Link的执行使得r成为v的子结点,从而实现两树的合并。Find-Depth(w):求出结点w的当前深度。¾¾在编译器的实现等应用中需要用到上述两类指令。如果采用前述的树结构形式,且Find-Depth指令不具路径压缩功能,则执行O(n)条Find-Depth指令,最坏情况下时间复杂度为O(n2);但如果采用具有路径压缩功能的Find-Depth指令,则原先树中在被压缩路径上的各结点深度会发生改变,如不采取其它措施,对其中某结点执行Find-Depth指令时,就会得到错误的深度信息。

2、如果我们给每个结点增加一个字段记录其在原树中的深度,这样,虽可在O(1)时间完成一条Find-Depth指令,但在执行Link指令时,由于以r为根的子树中结点的深度全部发生了变化,我们势必要修改该子树中所有结点的深度字段。此工作量很大,最坏情况下,O(n)条Link指令的时间复杂度也为O(n2);为了既能求得各点在原先树中的正确深度、又能使时间复杂度较小,我们需要使用具有路径压缩功能的Find-Depth指令;同时我们还需要采取一些辅助手段来保证深度计算的正确性。为此,我们对每个结点v增加2个字段(Count[v]和Weight[v]),并把经过改造的此类结点和树

3、所构成的森林称为D-森林。为减小时间复杂度,以下讨论的所有操作均是在D-森林中执行的,但我们必须保证它能正确反映原森林中任何结点在任何时刻的深度。在上例中,原先对左图中两子树执行Link(r,u)就成为了中图的形状;为使时间复杂度小,Link(r,u)在D-森林中执行后成为右图的形状。虽然形状变了,但我们只要保证在D-森林中执行Find-Depth时,一定能得到Find-Depth(r)=0,Find-Depth(u)=1,Find-Depth(w)=2;即保证Find-Depth能给出所有结点在原先森林中的正确深度即可。要实现这一点,首先需要对结点进行改造,即要

4、增加2个字段:Count[v]:记录在D-森林中以v为根的子树中结点的个数。Weight[v]满足下述性质:设在D-森林中执行指令Find-Depth(v),从v找到根结点a路径上的结点是vi1(=v)vi2vi3…vik(=a),则等于v在原树中的深度(注意不是在D-森林中的)。(如在上例中,应有Weight[u]=1,Weight[r]=-1,Weight[w]=1,这样就有,Depth(r)=Weight[r]+Weight[u]=0;Depth(u)=Weight[u]=1;Depth(w)=Weight[w]+Weight[u]=2。)请注意,初始时即任

5、何Link指令尚未执行(合并)时,不论是在原森林还是在D-森林中,所有结点均为单结点树,故所有结点的Weight值均为0即其深度为0。为了保证Weight值所具的性质,当在D-森林中执行Find指令实施路径压缩时,(即把vi1、vi2、vi3、…vi,k-2变为根结点a(即vik)的子结点时,另外,请注意vi,k-1原本就是根结点a的子结点)要使每一个结点vip(1≤p≤k-2)的新权变为,也就是:vip的新Weight值=vip的旧Weight值+vip原父结点的新Weight值要实现这一点可以有很多办法:既可以用递归、也可以用栈,甚至可以仅用while循环来实

6、现。下面介绍利用递归的思路:将原先的Find(i)指令改写为Find(i,w)指令:(原先的Find(i):ifip[i]thenp[i]Find(p[i]);returnp[i])注意,原先的Find程序调用后只是返回一个根结点编号,现在Find(i,w)调用返回时加送一个i的原父结点的新Weight值w,于是,按前面的讨论有:新Weight[i]=旧Weight[i]+w。但是vi,k-1(它的父亲是根a)是个例外,因为vi,k-1原先就是a的儿子。所以vi,k-1的Weight值应该保持不变。要做到这一点,只要Find从根a返回时,w中不放a的Weight值

7、而放一个0即可。这样,在执行这个经过修改的Find指令后,在原先从vi到根的路径上的所有结点的Weight值均已改变,(在vi之下的结点的Weight值不变),且仍满足Weight的性质。修改后的Find指令与原先的Find指令相比,每次调用执行只是增加了常数时间,故两者的时间复杂度同阶。作业:用三种方法(递归、栈和仅用while循环)来实现新Find,它不仅能实施路径压缩,而且在压缩时能正确地修改Weight值;注意尽可能避免使用全局变量,如写为Find(i,w,p,Weight),用四个参数变量。另外,编写完算法程序后要上机验证其正确性。Find-Depth要

8、给出结点v

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。