高级数据结构(下)ppt.ppt_第1页
高级数据结构(下)ppt.ppt_第2页
高级数据结构(下)ppt.ppt_第3页
高级数据结构(下)ppt.ppt_第4页
高级数据结构(下)ppt.ppt_第5页
已阅读5页,还剩152页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

JYP,1,高级数据结构 (下),教材: 数据结构(C+描述)(金远平编著,清华大学出版社),JYP,2,双连分量 (6.4.2),双连分量在连通性方面比一般的连通分量具有更高的要求,生成双连分量的操作也更复杂一些。 假设无向图G是连通的,下面给出双连分量的正式定义。 定义:G的顶点v是一个关节点当且仅当从G中删除v及其关联的边后,剩下的图至少有两个连通分量。,JYP,3,例如,在下面的连通图G6中,顶点1,4和7是关节点。,JYP,4,定义:双连通图是没有关节点的连通图。 例如,图G5是双连通的:,JYP,5,但图G6不是双连通的。 在表示通信网络的图中,边表示通信链路,顶点表示通信站点,关节点显然是薄弱环节。 定义:一个连通图G的双连分量是G的最大双连通子图。,JYP,6,图G6包含四个双连分量,如下所示:,JYP,7,不难发现,同一个图的两个双连分量最多有一个共同顶点。由此可推出,一条边不可能出现在两个或两个以上的双连分量中。因此,图G的双连分量划分E(G)。 图G的双连分量可利用G的任何深度优先生成树求得。,JYP,8,图G6的以顶点0为根的深度优先生成树如下:,JYP,9,其中,非树边用虚线表示。顶点旁的数字称为该顶点的深度优先数,简称为dfn。一个顶点的dfn表示该顶点在深度优先搜索中被访问的顺序。 例如,在前面的G6生成树中,dfn(0) = 1,dfn(1) = 2,以及dfn(7) = 5。 注意,在深度优先生成树中,如果顶点u是v的祖先,则dfn(u) dfn(v)。,JYP,10,相对于生成树T,当且仅当u是v的祖先或v是u的祖先时,非树边 (u, v) 才是一条回边。 例如,(4, 1) 和 (6, 7) 是回边。 不是回边的非树边称为横边。根据深度优先搜索的规律,相对于任意一个图的任何深度优先生成树,该图不可能有横边。,JYP,11,因此,深度优先生成树的根是关节点的充分必要条件是它至少有两个子女。 任何其它顶点u是关节点的充分必要条件是u至少有一个子女w,使得经过只由w,w的后代以及一条回边构成的路径不可能到达u的祖先,因为删除顶点u及其关联的边将使w及其后代与u的祖先断开联系。,JYP,12,假设顶点w的祖先包括w本身。 为了表示一个顶点经过其后代以及一条回边所能到达的最高祖先,对于图G的每个顶点w,定义low(w) 为从w经过其后代以及一条回边所能到达的最高祖先的dfn。 显然,low(w)是从w经过其后代以及一条回边所能到达的顶点的dfn中最低的,并可由以下公式计算: low(w) = min dfn(w), min low(x)| x是w的一个子女, min dfn(x)| (w, x) 是一条回边,JYP,13,于是,u是关节点的充分必要条件是:u或者是至少有两个子女的深度优先生成树的根,或者u不是根结点但有一个子女w,使得low(w)dfn(u)。 下面是G6的以顶点0为根的深度优先生成树中各顶点的dfn和low值:,JYP,14,修改DFS可得到计算一个连通图各顶点的dfn和low值的函数DfnLow: void Graph:DfnLow (const int x ) / 在顶点x开始DFS num = 1; / num是Graph 的类型为int的数据成员 dfn = new intn; low = new intn; / dfn和low都是Graph 的 / 类型为int *的数据成员 for ( int i = 0; i n; i+ ) dfni = lowi = 0; DfnLow ( x, -1 ); / x是根,其双亲是伪顶点-1 delete dfn; delete low; ,JYP,15,void Graph:DfnLow ( int u, int v ) / 从u开始深度优先搜索并 / 计算dfn和low。v是u的双亲 dfnu = lowu = num+; for (每一个与u邻接的顶点w) / 具体代码与图的表示有关 if (dfnw = 0) / w 是未被访问顶点 DfnLow (w, u); lowu = min2 (lowu, loww); / min2(x,y)返回x和y的 / 较小者 else if (w != v) lowu = min2 ( lowu, dfnw ); / 回边。注 / 意(v, u)不是回边 ,JYP,16,注意,在深度优先生成树中,若v是u的双亲,则 (u, v) 一定不是回边。 函数DfnLow(u, v)的参数v就是为区分这种情况而设的。 深度优先搜索的第一个顶点x无双亲,因此对其的调用形式为DfnLow(x, 1)。 函数DfnLow(u, v)用到的另一个函数min2返回其两个参数的较小者。,JYP,17,在DfnLow的基础上进一步处理,可以将连通图的边划分为双连分量。 注意,当DfnLow(w, u)返回后,loww已计算好。如果lowwdfnu,则可确定一个新的双连分量。 通过将搜索时首次遇到的边存入栈中,可以求得一个双连分量的全部边。,JYP,18,设深度优先搜索最近访问的顶点是u,且顶点w与u邻接但不是u的直接双亲,则在以下两种情况中,(u, w)是首次遇到的边: (1)w是未被访问的顶点 (2)w是已被访问的顶点而且是u的祖先 由于未被访问的顶点的dfn值初始化为0,祖先的dfn值小于后代的,所以两种情况都可归结为 dfnw dfnu。,JYP,19,注意:如果dfnw dfnu,则边(w,u)一定已经作为回边(当处于w点时)加到栈中,如下所示:,u,x,w,2,3,4,JYP,20,函数Biconnected实现了上述过程: void Graph:Biconnected ( ) num = 1; dfn = new intn; low = new intn; for ( int i = 0; i 1。 dfnu = lowu = num+;,JYP,21,for (每一个与u邻接的顶点w) / 具体代码与图的表示有关 if (v != w / 回边 / for结束 ,JYP,22,Biconnected的时间复杂性是O(n + e)。 注意,函数Biconnected假设输入的连通图至少有两个顶点。 只有一个顶点的连通图无边,但按定义,它们也是双连通的。对此可作特殊处理。,JYP,23,求解最小生成树的普瑞姆算法(6.5.2),设TV是最小生成树的已选顶点集合,T是最小生成树的已选边集合。普瑞姆算法首先任选图G中一个顶点u,将u加入TV中。 然后将一条代价最小的边 (u, v) 加入T中,使得T (u, v)仍然是一棵树。 重复上述步骤,直到T包含n 1条边为止。 注意,(u, v) 关联的两个顶点必有一个在TV中,另一个不在TV中。,JYP,24,普瑞姆算法的框架: TV = 0; / 从顶点0开始构造,假设G至少有一个顶点 for (T = ; T包含的边少于n -1条; 将(u, v)加入T) 令 (u, v) 为满足 u TV 且 v TV 的代价最小的边; if (不存在这样的边) break; 将v加入TV; if (T包含的边少于n-1条) cout “不存在最小生成树” endl ;,JYP,25,用普瑞姆算法构造下图的最小生成树的过程:,JYP,26,JYP,27,JYP,28,JYP,29,设 是不属于TV的顶点集合。 对于任何v ,定义nearv为TV中使 cost(nearv, v)最小的顶点(若(v, w)E,则设cost(v, w) = ),则 cost(nearv,v) = 。 下一个加入TV的顶点v应满足:v ,且cost(nearv,v) = 。下一条加入T的边自然是 (nearv,v)。,JYP,30,设w是 中与v邻接的顶点。顶点v加入TV之后,如果cost(nearw,w) cost(v, w),则将nearw改为v。 由此可以有效地实现普瑞姆算法。 如果用邻接矩阵costij表示图G,则算法的时间复杂性是O(n2),因为算法总共选n 1个顶点,每选一个顶点v及处理v对nearw(w 且w与v邻接)的影响最多只需O(n)时间。,JYP,31,如果用邻接表表示图G并利用斐波纳契堆,则可使算法的性能更好。对于v ,定义distv = cost(nearv,v),可理解为顶点v到已构造的部分最小生成树的最近距离。 每次往TV中加入一个顶点,算法都需要确定顶点v,使得v ,且distv = 。这对应于 上的删除最小元素操作。 由于v加入TV, 中与v邻接的顶点的dist值可能减少。这对应于 上的关键字减少操作。,JYP,32,关键字减少操作的总次数最多是图中边的条数。删除最小元素操作的总次数是n 1。 初始时, 含n 1个顶点。如果以dist为关键字,将 组织为斐波纳契堆,则需要n 1次插入操作初始化斐波纳契堆。 接着需要执行n 1次删除最小元素操作和最多e次关键字减少操作。所有这些操作的代价是各操作的分摊代价之和,即 O(n log n + e)。 因此,算法的时间复杂性变为O(n log n + e)。当e远小于n2时,这显然是一种改进。,JYP,33,斐波纳契堆在最短路径算法中的应用,先回忆一下经典的最短路径算法: 1 void Graph:ShortestPath(const int n, const int v) 2 for (int i = 0; i n; i+) 3 si = FALSE; disti = lengthvi; 4 if ( i != v ,JYP,34,10 for ( int w = 0; w n; w+) 11 if (!sw) 12 if (distu + lengthuw distw) distw = distu + lengthuw; pathw = u; 13 / for (i = 0;) 结束 14,JYP,35,分析:第2行的for循环需要O(n)时间。第7行的for循环执行n 2次,每次需要O(n)时间用于第8行的选择和第10到12行的更新dist值。因此,该循环的总时间是O(n2)。 整个算法的时间是O(n2)。 即使采用邻接表,第10到12行的总时间可减少到O(e)(因为只有邻接自u的顶点的dist可能变化),第8行的总时间仍然是O(n2)。,JYP,36,应用斐波纳契堆和邻接表,可使算法的时间复杂性减少为O(n log n + e)。 每次迭代,都需要确定顶点u,使得u ,且distu = 。这对应于 上的删除最小元素操作。 由于u加入S, 中与u邻接的顶点的dist值可能减少。这对应于 上的关键字减少操作。,JYP,37,初始时, 含n 1个顶点。如果以dist为关键字,将 组织为斐波纳契堆,则需要n 1次插入操作。 接着需要执行n 2次删除最小元素操作和最多e次关键字减少操作。 所有这些操作的代价是各操作的分摊代价之和,即 O(n log n + e)。 因此,算法的时间复杂性是O(n log n + e)。 当e远小于n2时,这种实现显然更好。 考察题:P223 23(每个同学单独完成,并提交报告,作为本课程主要成绩因素),JYP,38,基于链表和映射表排序结果的顺序化(7.8),对于基于链表的排序结果,有时需要按次序就地重新排列,使它们在物理上也是顺序的。 设记录表R0, , Rn-1经排序后的结果是一个按关键字非递减次序链接的链表,且first是链表的首记录指针。 将记录R0和Rfirst交换。如果first 0,则表中应有一个记录Rx,其link字段值为0。如果能够修改Rx的link字段,使其指向原位于R0的记录的新位置first,则剩余记录R1, , Rn-1也是按关键字非递减次序链接的。,JYP,39,但在单链表中,我们无法快速确定结点R0的前驱Rx。于是可将R0的link字段设置为first,表示原位于R0的记录已移到Rfirst。 这样,R0还作为R1, , Rn-1链表中的虚拟结点。借助此虚拟结点,我们可找到剩余记录链表的首结点。 重复上述过程n1次即可完成重新排列。 一般地,设记录表R0, , Ri-1已在物理上按序排列,Rfirst是剩余记录Ri, , Rn-1链表的首记录,记录Ri和Rfirst交换后,将新Ri记录的link字段设置为first,表示原位于Ri的记录已移到Rfirst。,JYP,40,同时,注意到作为剩余记录Ri, , Rn-1链表的首记录下标的first总是大于或等于i,我们可以经过虚拟结点,找到剩余记录链表的首记录下标。 函数list实现了上述方法: template void list(Element *list, const int n, int first) / 重新排序由first指向的链表中的记录,使list0,listn-1 / 中的关键字按非递减次序排列 for (int i = 0; i n 1; i+) / 找到应放到位置i的记录。由于位置0, 1, , i-1的记录已 / 就位,该记录下标一定i while (first i) first = listfirst.link; / 经过虚拟结点,JYP,41,int q = listfirst.link; / listq是按非递减次序的下一个 / 记录,可能是虚拟记录 if (first != i) / 交换listi 和listfirst,并将listi.link / 设置为原listi的新位置 Element t = listi; listi = listfirst; listfirst = t; listi.link = first; first = q; ,JYP,42,例7.9 对 (26, 5, 77, 1, 61, 11, 59, 15, 48, 19) 进行链表排序后,所得链表如下所示:,JYP,43,list的for循环每次迭代后记录表的状态如下,变化用粗体字表示,虚拟结点的link字段用带下划线的字体表示:,JYP,44,JYP,45,JYP,46,JYP,47,JYP,48,对list的分析:设有n个记录,for循环迭代n1次。每次最多交换2个记录,需要3次记录移动。如果每个记录的长度为m,则每次交换的代价是3m。所以,最坏情况下记录移动的总代价是O(mn)。 在while循环中,任何结点最多被检查一次,所以while循环的总时间是O(n)。 显然,list所需的辅助空间是O(m)。,JYP,49,链表排序不适用于希尔排序、快速排序和堆排序,因为记录表的顺序表示是这些方法的基础。 对于这些方法可以采用映射表t,表的每一个单元对应一个记录。映射表单元起着对记录间接寻址的作用。 排序开始时,ti = i,0in1。如果要求交换Ri和Rj,则只需交换表单元ti和tj。排序结束时,关键字最小的记录是Rt0,最大的记录是Rtn-1,所要求的记录排列是Rt0, Rt1, , Rtn-1,如下一页所示。,JYP,50,JYP,51,有时为了避免间接寻址,还需要根据映射表t确定的置换在物理上重新排列记录。 整个置换由不相交的环路组成。含记录i的环路由i, ti, t2i, , tki构成,且tki = i。 例如,上一页的置换由两个环路组成,第一个包含记录R0和R4,第二个包含记录R1,R3和R2。 函数table首先沿着包含R0的环路将记录移到其正确位置。接着,如果包含R1的环路未被移动过,则沿着该环路将记录移到其正确位置。由此继续移动包含R2, R3, , Rn-2的环路,最终得到物理上就序的记录表。,JYP,52,template void table(Element *list, const int n, int *t) / 重新排列list0, , listn-1,使其对应序列listt0, , / listtn-1, n1 for (int i = 0; i p = listi; int j = i; do int k = tj; listj = listk; tj = j; j = k; while ( tj != i ); listj = p; / p中的记录应该移到位置j tj = j; ,JYP,53,例7.10 一个根据映射表t对记录顺序化的例子:,JYP,54,对table的分析:设每个记录占用m个存储单元,则所需辅助空间为O(m)个存储单元。 for循环执行了n1次。如果对于某些i的取值,ti i,则存在一个包含k 1个不同记录Ri, Rti, , Rtk-1i的环路。重新排列这些记录需要k+1次移动。 设kj是在for循环中i = j时以Rj开头的非平凡环路的记录个数。对于平凡环路,则令kj = 0。记录移动的总次数是,JYP,55,当 = n且存在n/2个非平凡环路时,记录移 动的总次数达到最大值 3n/2。 移动一个记录的代价是O(m),总的计算时间是O(m n)。,JYP,56,二叉查找树的结合与分裂 (8.2.3),首先回顾二叉查找树的定义: 二叉查找树是一棵二叉树。如果不空,该树应满足以下性质: (1) 每个元素有一个关键字,且任何两个不同的元素的关键字不相等(即关键字唯一); (2) 左子树(如果存在的话)中的关键字小于根结点中的关键字; (3) 右子树(如果存在的话)中的关键字大于根结点中的关键字; (4) 左、右子树也是二叉查找树。,JYP,57,二叉树的例子:,其中,(a)不是二叉查找树,(b)和(c)是。,JYP,58,除了查找、插入和删除操作以外,有的应用还需要对二叉查找树进行下列操作: (1) C.ThreeWayJoin(A, x, B): 构建C,C由原来在A和B中的元素以及元素x构成。假设A中元素的关键字小于x.key,B中元素的关键字大于x.key。最后将A和B设置为空。 (2) C.TwoWayJoin(A, B): 构建C,C由原来在A和B中的元素构成。假设A中所有元素的关键字小于B中所有元素的关键字。最后将A和B设置为空。,JYP,59,(3) A.Split(i, B, x, C): 分裂为三部分:B包含A中所有关键字小于i的元素;如果A含关键字为i的元素,则将该元素复制到x,并返回x的指针,否则返回0;C包含A中所有关键字大于i的元素。最后将A设置为空。,JYP,60,3-路结合的实现: 获得一个新结点,使其成为C的root,并将其data字段设置为x,LeftChild字段设置为A.root,RightChild字段设置为B.root。 最后将A.root和B.root设置为0。 计算时间是O(1),新树C的高度是 maxheight(A), height(B)+1。,JYP,61,2-路结合可通过3-路结合实现: 如果A(或B)是空树,则将C.root设置为B.root(或A.root),并将B.root(或A.root)设置为0即可。 当A和B都不空时,首先从A中删除关键字最大的元素x,由此得到A。再执行3-路结合操作C.ThreeWayJoin(A, x, B)即可完成整个操作。 计算时间是O(height(A),新树C的高度不超过 maxheight(A), height(B)+1。,JYP,62,分裂操作的实现: 在根结点(即i = A.rootdata.key)的分裂很容易。这时,B是A的左子树,x是根结点元素,C是A的右子树,如图8.4(a)所示。 如果i小于根结点的关键字,根结点及其右子树应属于C,如图8.4(b)所示。 如果i大于根结点的关键字,根结点及其左子树应属于B,如图8.4(c)所示。,JYP,63,JYP,64,一般地,可以在A中向下查找关键字为i的元素的过程中构造二叉查找树B和C。设t指向当前结点。 若i tdata.key,则结点t及其左子树应加入B中。 若i = tdata.key,则应将t的左、右子树分别加入B、C中,并将tdata复制到x。,JYP,65,由于当前C中已有关键字一定大于新加入部分的关键字,所以新加入部分应作为当前C中最小关键字所在结点(用L指向)的左子树,如下所示:,JYP,66,同理,新加入B部分应作为当前B中关键字最大元素所在结点(用R指向)的右子树。 为了避免判断树为空的情况,在开始时为B和C分别引入头结点Y和Z。下面是实现分裂操作的算法: template Element* BST:Split(Type i, BST,JYP,67,BstNode *t = root; while (t) if (i = tdata.key) / 在结点t分裂 RRightChild = tLeftChild; LLeftChild = tRightChild; x = tdata; delete t; B.root = YRightChild; delete Y; / 删除头结点 C.root = ZLeftChild; delete Z; / 删除头结点 root = 0; return ,JYP,68, else RRightChild = t; R = t; t = tRightChild; RRightChild = LLeftChild = 0; / 注意这是必要的 B.root = YRightChild; delete Y; / 删除头结点 C.root = ZLeftChild; delete Z; / 删除头结点 root = 0; return 0; ,JYP,69,对Split的分析:while循环始终保证以t为根的子树中的所有关键字大于正在构造的B中关键字,小于正在构造的C中的关键字。由此容易证明算法的正确性。 算法的时间复杂性是O(height(A)。B和C的高度不超过A的高度。,JYP,70,二叉查找树的性能分析 (8.2.4),为了分析二叉查找树的性能,再次引用扩展二叉树的概念,即用方结点替代所有空二叉子树。 这些方结点又称为外部结点。 二叉树原来的(圆)结点称为内部结点。,JYP,71,图8.1(b)的扩展二叉树如下所示:,JYP,72,n个结点的二叉树有n + 1个外部结点。不成功的查找都会在某一个外部结点结束,所以也称外部结点为失败结点。 二叉树的外部路径长度E定义为所有外部结点到根结点的路径长度之和。 内部路径长度I是所有内部结点到根结点的路径长度之和。 图8.6的内部路径长度是 I = 0 + 1 + 1 + 2 = 4 其外部路径长度E是 E = 2 + 2 + 2 + 3 + 3 = 12,JYP,73,引理8.1:如果二叉树T有n 个(n0)内部结点,I是其内部路径长度,E是其外部路径长度,则 E = I + 2n。 证明:对n应用归纳法。 当n = 0,E = I = 0,引理8.1成立。 假设n = m时引理8.1也成立。 考虑一棵有m + 1个内部结点的树,设该树的内部路径长度为I,外部路径长度为E。设v是该树中的内部结点,且v的左、右子女都是外部结点。设k是结点v到根结点的路径长度。,JYP,74,将v的两个子女从树中删除,使v成为新的外部结点,树的内部结点个数减少为m,内部路径长度减少为I k。v的每个子女到根结点的路径长度是k + 1,所以外部路径长度应减少2(k + 1)再加上新外部结点v到根结点的路径长度k。 因此,新树的外部路径长度是 E 2(k + 1) + k = E k 2 根据归纳假设, E k 2 = (I k) + 2m 整理可得 E = I + 2(m + 1) 因此,当n = m + 1时引理8.1也成立。,JYP,75,查找二叉查找树的时间依赖于所考察的内部结点个数,假设一个内部结点的计算时间用一次比较度量,下面分析具有n个内部结点的二叉查找树的性能。,JYP,76,1 最坏情况 根据引理8.1,具有最大I的扩展二叉查找树也具有最大的E。 在二叉树完全偏斜时I达到最大值。这时, I = = 因此,在最坏情况的二叉查找树中进行成功查找的平均比较次数Sn为 Sn = = (8.1),JYP,77,2 最好情况 为了使I最小,应使尽可能多的内部结点靠近根结点。在与根结点的距离为1处最多可有2个结点,距离为2处最多可有4个结点,一般地,最小的I是 0 + 2 1 + 4 2 + 8 3 + + 完全二叉树就是一种具有最小内部路径长度的树。采用完全二叉树的结点编号,结点i到根结点的距离是log2i。这样,最小的I是 I =,JYP,78,利用数学推导可得: = (n + 1)q 2(q + 1) + 2, 其中,q = log2(n + 1) 因此,在最好情况的二叉查找树中进行成功查找的平均比较次数Sn为 Sn = = log2(n + 1) 1log2n1 (8.2),JYP,79,3 平均情况 Sn 平均成功查找所需的比较次数 Un 平均不成功查找所需的比较次数 在树中查找到任何关键字所需的比较次数正好是含该关键字的元素首次插入所需的比较次数加1,而插入该元素所需的比较次数与该元素不在树中的不成功查找的相同。 该元素不在树中的不成功查找等概率地出现在树中含0, 1, , n 1个结点的情况。由此可得: Sn = 1 +,JYP,80,同时,Sn = ,Un = ,E = I + 2n,所以, Sn = = 即 Sn = Un 1 (8.3),JYP,81,又由 Sn = 和 Sn = 1 + 可得 I = U0 + U1 + + Un-1 再由 Un = = 可得,JYP,82,(n + 1)Un = 2n + U0 + U1 + + Un-1 为解此递归式,用n 1替换n: n Un-1 = 2(n 1) + U0 + U1 + + Un-2 两式相减,得: Un = Un-1 +,JYP,83,由于U0 = 0,所以, Un = 2 = 2 Hn+1 2 其中,Hn+1是第n + 1个调和数,即 Hn+1 = 根据调和数理论,Hn ln n + 0.6,Un 2ln n。 由于ln n = (ln 2) (log2n),所以, Un 2 (ln 2) (log2n) 1.39 log2n (8.4),JYP,84,由(8.3)式, Sn 1.39 log2n 1。,JYP,85,最佳二叉查找树 (8.2.5),如果一个符号表固定,只对其进行查找操作,则称其为静态符号表。 电子词典就可以看成是一个静态符号表,且在实际应用中人们对不同单词的查找概率是不同的。 下面讨论表示静态符号表的二叉查找树的构造问题。 当查找各标识符的概率相同时,可以用最好情况二叉查找树表示该符号表。,JYP,86,当查找各标识符的概率不相同时,完全二叉树不一定是最佳的。 直觉上,查找概率越大的标识符越靠近根结点性能越好。 这就要求我们为标识符查找概率不相同的符号表构造最佳二叉查找树。 设需要构造的二叉查找树包含标识符a1, a2, , an,且a1 a2 an,查找每个ai,的概率是pi,则当查找只限于成功情况时,该二叉查找树的代价是,JYP,87,不成功查找在算法Search检查到失败结点时结束。不在二叉查找树中的标识符可被划分为n+1个类Ei,0in。 E0包含所有满足x an的标识符x。 对于Ei中的所有标识符,查找都会在同一个失败结点结束,且对于不同类中的标识符,查找会在不同的失败结点结束。 将失败结点从0到n编号,编号i的失败结点对应Ei,0in。,JYP,88,设qi是所查找的标识符属于Ei的概率,则全部失败结点的代价是 该二叉查找树的总代价是 (8.5) 表示a1, a2, , an的最佳二叉查找树应使(8.5)式的值最小。,JYP,89,例8.1 图8.8给出了用于表示a1, a2, a3 = (data, pipe, work)的所有可能的二叉查找树:,JYP,90,JYP,91,当pi = qj = 1/7时,1i3,0j3,有 树(a)的代价 = 15/7 树(b)的代价 = 13/7 树(c)的代价 = 15/7 树(d)的代价 = 15/7 树(e)的代价 = 15/7 正如可以预料到的,树(b)是最佳的。,JYP,92,当p1 = 0.5,p2 = 0.05,p3 = 0.1,q0 = 0.15,q1 = 0.05,q2 = 0.1,和q3 = 0.05时,有 树(a)的代价 = 2.55 树(b)的代价 = 1.95 树(c)的代价 = 1.6 树(d)的代价 = 2.05 树(e)的代价 = 1.55 树(e)是最佳的。,JYP,93,采用例8.1的穷举方法确定代价最小的树计算复杂性很高。当n较大时,这种方法是没有实用价值的。 通过利用最佳二叉查找树的一些性质,则可以得到相当高效的算法。 设Tij表示包含ai+1, , aj(i j)的最佳二叉查找树,则Tii(0in)是空树,且对于j i,Tij无定义。 设cij为Tij的代价。由定义,cii = 0。 设rij为Tij的根结点标识符的下标号。,JYP,94,再设 wij = qi + 为Tij的权重。由定义,wii = qi,0in。 于是,T0n是包含标识符a1, a2, , an的最佳二叉查找树,其代价是c0n,其根结点标识符的下标是r0n。,JYP,95,如果Tij是包含ai+1, , aj的最佳二叉查找树,且rij = k,则i kj。Tij有左、右两棵子树,如下图所示:,JYP,96,L是左子树,包含标识符ai+1, , ak-1;R是右子树,包含标识符ak+1, , aj。 根据(8.5),Tij的代价 cij = pk+L的代价+R的代价+L的权重+R的权重 其中,L的权重 = wi,k-1,R的权重 = wkj。 要使cij最小,L的代价应等于ci,k-1,R的代价应等于ckj,因此 cij = pk+ci,k-1+ckj+wi,k-1+wkj = wij+ci,k-1+ckj (8.7),JYP,97,由于Tij是最佳的,根据(8.7)式,rij = k应满足 wij + ci,k-1 + ckj = 或 ci,k-1 + ckj = (8.8) 根据(8.7)和(8.8)式,并利用动态规划方法,可以从Tii = 和cii = 0开始,逐步得到T0n 和c0n。,JYP,98,例8.2 设n = 3,(a1, a2, a3) = (data, pipe, work),(p1, p2, p3) = (0.5, 0.05, 0.1),(q0, q1, q2, q3) = (0.15, 0.05, 0.1, 0.05)。 初始时,wii = qi,cii = 0,0i3。利用(8.7)和(8.8)式,并注意到wij = wi,j-1 + pj + qj,可得 w01 = w00 + p1 + q1 = 0.15 + 0.5 + 0.05 = 0.7 c01 = w01 + minc00 + c11 = 0.7 r01 = 1 w12 = w11 + p2 + q2 = 0.05 + 0.05 + 0.1 = 0.2 c12 = w12 + minc11 + c22 = 0.2 r12 = 2,JYP,99,w23 = w22 + p3 + q3 = 0.1 + 0.1 + 0.05 = 0.25 c23 = w23 + minc22 + c33 = 0.25 r23 = 3 在wi,i+1和ci,i+1的基础上(0i 3),再次利用(8.7)和(8.8)式,可计算出wi,i+2、ci,i+2和ri,i+2,0i 2。重复此过程,最终可得到w03、c03和r03。 下一页的图8.10给出了此计算结果。,JYP,100,JYP,101,由此,c03 = 1.55是最小代价,T03的根结点含标识符a1,其左子树是T00,右子树是T13。 T13的根结点含标识符a3,其左子树是T12,右子树是T33。 T12的根结点含标识符a2,其左子树是T11,右子树是T22。由此可以构造T03,如右图所示。,JYP,102,由于本例子中假设的pi和qi与上一个例子的相同,所以该树在结构上与上一个例子的最佳二叉查找树相同。 由上可得计算cij和rij(0i n,i jn)以及根据rij构造T0n的方法:按(j i)= 1, 2, , n的顺序计算cij。 当j i = m时,需要计算n m + 1个cij。每计算一个cij需要从m个量中选择最小的((8.8)式),计算时间是O(m)。计算所有cij的总时间为O(nm m2)。,JYP,103,计算全部cij和rij的总时间是 = O(n3) Knuth的研究成果表明,(8.8)式中的最佳u的选择可限定在ri,j-1uri+1,j的范围。 因此,当j i = m时,1r0,m-1r1,mr2,m+1 rn-m+1,nn,总计算时间改进为 2n m + 1 = O(n),JYP,104,当j i = m,且m = 1时的总计算时间为n m + 1。计算全部cij和rij的总时间改进为 n m + 1 + = O(n2) 假设二维数组w、c和r是类BST的私有数据成员。算法obst实现了上述方法,并根据计算结果调用函数build构造最佳二叉查找树。,JYP,105,template void BST:obst(float *p, float *q, Element*a, int n) / 给定n个标识符a1 a2 an,和pj(1 j n)和 / qi(0 i n),计算表示ai+1, aj的Tij的cij,同时计算 / rij 和wij。最后调用build构造最佳二叉查找树。 for (int i = 0; i n; i+) wii = qi; cii = 0; / 初始化 wii+1 = qi + qi+1 + pi+1; / 只含一个结点的情况 rii+1 = i+1; cii+1 = wii+1; wnn = qn; cnn = 0;,JYP,106,for (int m = 2; m = n; m+) / 含m个结点的最佳二叉查找树 for (i = 0; i = n - m; i+) int j = i + m; wij = wij-1 + pj + qj; int k; float s = MAX; / 设MAX是已定义的最大值常数 for (int u = rij-1; u = ri+1 j; u+) float t = ciu-1 + cuj; if (t s) s = t; k = u; / 求k cij = wij + cik-1 + ckj; / (8.7)式 rij = k; root = build(a, 0, n); / obst结束,JYP,107,template BstNode* BST:build(Element*a, int i, int j) / 根据rij构造最佳二叉查找树 if (i = j) return 0; / 空树 BstNode*p = new BstNode; int k = rij; pdata = ak; pLeftChild = build(a, i, k-1); pRightChild = build(a, k, j); return p; 显然,build(a, 0, n)的计算时间是O(n)。,JYP,108,8.6.6 B+树,B树只有利于单个关键字查找,而在数据库等许多应用中常常也需要范围查询。 为了满足这种需求,需要改进B树。 B+树就是这种改进的结果,也是现实中最常用的一种B树变种。 B+树与B树的最大区别是:B+树的元素只存放在叶结点中。 不是叶的结点又称为中间结点。中间结点也存放关键字,但这些关键字只起引导查找的“路标”作用。,JYP,109,定义:一棵m阶B+树或者为空,或者满足下列性质: (1) 中间结点最多有m棵子树,且具有下列结构: n, A0, (K1, A1), (K2, A2), , (Kn, An) 其中,Ai是子树指针,0in m,Ki是关键字,1in m。 (2) Ki Ki+1,1i n,且所有中间结点的关键字互不相同。 (3) Ai中的所有关键字都大于等于Ki并小于Ki+1,0 i n。,JYP,110,(4) An中的所有关键字都大于等于Kn,A0中的所有关键字都小于K1。 (5) 根结点至少有2棵子树,其它中间结点至少有m/2棵子树。 (6) 所有叶结点都处于同一个层次,包含了全部关键字以及相应的元素或元素地址,叶结点中的关键字从小到大排序,且互不相同。 (7) 叶结点中存放的关键字个数可以大于或小于m。设mleaf是叶结点可容纳的最大失败结点个数,则其中的实际关键字个数n应满足:1mleaf/2 1n mleaf。,JYP,111,B+树的叶结点被链接成双链表,以便范围查询。 图8.30是一个B+树的例子:,其中,m=3,mleaf=5。以后的例子都假设m=3,mleaf=5。,JYP,112,除了需要一直查到叶结点以外,B+树的查找方法与B树的基本相同。 即使中间结点中已有需要查找的关键字,但那也只是“路标”,并不提供实际元素的地址。 例如,在图8.30中查找35。35在根结点中,表示关键字为35的元素在第2棵子树中。由根结点的第2棵子树的第1个分枝,可到达关键字为35的元素所在的叶结点。,JYP,113,往B+树中插入关键字为x的元素的方法与B树的类似。 首先,定位到关键字为x的元素可插入的叶结点p。 如果结点p不满,则加入新元素,并将修改后的结点p写到磁盘即可。 如果结点p已满,则将其分裂为p和q两个结点,这两个结点平均承载原来结点p中的内容和新元素,且结点q中元素的关键字大于结点p中的。再将结点q中最小关键字和指针q插入结点p的双亲。,JYP,114,这又可能使双亲结点分裂,直至使根结点分裂,整个B+树长高一层。 图8.31通过例子描述了上述插入过程,其中,中间结点的粗体字表示新插入的“路标”,叶结点的粗体字表示新插入的关键字。,JYP,115,图8.31 1,JYP,116,图8.31 2,JYP,117,从B+树中删除关键字x的方法也与B树的类似。 首先,定位到关键字x所在的叶结点p。 如果删除后结点p中的关键字个数仍然大于等于 mleaf/21,则将修改后的结点p写到磁盘即可。,JYP,118,例如,从图8.30的B+树中删除30,,JYP,119,得到图8.32的B+树。注意,虽然元素30已被删除,但作为“路标”的30不必从中间结点中删除。,JYP,120,如果删除后结点p中只有 mleaf/2 2个关键字,且其最邻近兄弟q至少有mleaf/2个关键字,则可从结点q移一个到结点p,从而使这两个结点都满足要求。 此过程还需要改变双亲结点中的“路标”,以反映结点p或q中第一个关键字的值。,JYP,121,例如,从图8.32的B+树中删除31,使得第2个叶结点中的28被移来替代其原来的位置,得到图8.33的B+树。,JYP,122,如果删除后结点p中只有 mleaf/2 2个关键字,且其最邻近兄弟q只有mleaf/2 1个关键字,则需要将结点q的内容合并到结点p,并删除整个结点q。 这又可能导致双亲结点关键字个数不足,引起新一轮的旋转与合并,直至删除根结点。,JYP,123,图8.34描述了从图8.33的B+树中删除35的过程,注意,“路标”28移到根结点,35移到根结点的右子女。,图8.34 1,JYP,124,图8.34 2,JYP,125,实验作业: 设计一个磁盘资源管理系统,实现B+树的查询、插入和删除操作,并生成测试数据集,验证这些操作的正确性。,JYP,126,动态散列 (8.9),静态散列必须静态分配散列表空间。 如果分配的表空间过大,则会浪费空间;如果分配的表空间过小,则会导致冲突频繁,而且当数据量大于散列表的容量时整个散列表需要重组。 动态散列又称为可扩展散列,其目的就是要既保持静态散列的快速查找性能,又具备动态适应数据文件大小变化的能力。 假设文件F是记录R的集合。每个记录有一个关键字key。记录存储在页面(或桶)中,每个页面的容量是p个记录。,JYP,127,在设计算法时,应尽量减少对页面的访问次数,因为页面通常存储在磁盘上。

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论