匙末苛厄拇捕芬糕谁淳遭寂涤配晾困实藉滨琉熏夯和饲障毁共瞧含逐惺辣高级数据结构高级数据结构高级数据结构高级数据结构 教材：教材：数据结构（数据结构（C+描述）（金远平编著，清华大描述）（金远平编著，清华大学出版社）学出版社）讲课教师：讲课教师： 金远平，软件学院金远平，软件学院 ypjinseu.edu.cn淆汽肺孰斯渺粒崔椰嚣表盐声瞒遮迸泰没凿故研喳屉址熬邹释谍掸椒版咬高级数据结构高级数据结构1JYP代价分摊（代价分摊（1.5.4） 将孤立地分析一次算法调用得出的结论应用于一将孤立地分析一次算法调用得出的结论应用于一个个ADT的相关操作序列会产生过于悲观的结果。的相关操作序列会产生过于悲观的结果。例例1.12 整数容器整数容器Bag。class Bag public: Bag ( int MaxSize = DefaultSize ); / 假设DefaultSize已定义 int Add (const int x ); / 将整数x加入容器中 int Delete (const int k ); / 从容器中删除并打印k 个整数private: int top; / 指示已用空间 int *b; / 用数组b存放整数 int n; / 容量;供忱棚坍永从郁橡椎在闪投窒恶傀廓绅挖塑吮丘暇举掣煌弘懈留掘骏蓑熙高级数据结构高级数据结构2JYP各操作的实现如下：各操作的实现如下：Bag:Bag ( int MaxSize = DefaultSize ):n(MaxSize) b = new intn; top = -1; int Bag:Add (const int x) if (top = = n-1) return 0; / 返回0表示加入失败 else b+top = x; return 1; 浴鹰栋独沛瓣湃衣旷器蛙慌筐侯很缅初烂苔超槛龚惯进埃书硷痘绦删涌出高级数据结构高级数据结构3JYPint Bag:Delete (const int k) if (top + 1 k ) return 0; /容器内元素不足容器内元素不足k k个，删除失个，删除失败败 else for (int i = 0; i k; i+) cout btop i “ ” ; top = top - k; return 1; 先分析操作成功的情况：先分析操作成功的情况：Add(x)的时间复杂性的时间复杂性是是O(1)；Delete(k)需要需要k个程序步，且个程序步，且k可能等于可能等于n，在最坏情况下其时间复杂性是在最坏情况下其时间复杂性是O(n)；一个调用；一个调用Add操作操作 m1次，次，Delete操作操作m2次的序列的总代价则为次的序列的总代价则为O(m1+ m2n)。辜溯拔闪惺琼砍舵睦卸揍拦同沙狸哈牙养肘匝拷竹沽友仅兄酿砸疑怎咽栅高级数据结构高级数据结构4JYP 前面是常规分析的结论。进一步观察：如果一开前面是常规分析的结论。进一步观察：如果一开始容器为空，则删除的元素不可能多于加入的元素，始容器为空，则删除的元素不可能多于加入的元素，即即 m2 次次Delete操作的总代价不可能大于操作的总代价不可能大于m1 次次Add操作的总代价。因此，在最坏情况下，一个调用操作的总代价。因此，在最坏情况下，一个调用Add操作操作 m1次，次，Delete操作操作m2次的序列的总代价为次的序列的总代价为O(m1)。 操作失败时，操作失败时，Add(x)和和Delete(k) 的时间复杂性的时间复杂性都是都是O(1)。因此，在操作可能失败的情况下，一个。因此，在操作可能失败的情况下，一个调用调用Add操作操作 m1次，次，Delete操作操作m2次的序列的总代次的序列的总代价为价为O(m1+ m2)。纲枝痉雾两亦沃芭宫倚综摸澜灿息锁诀奢绢东叠荡锥谓姥输巧苍待失范扒高级数据结构高级数据结构5JYP 常规分析并没有错，只是其推导出的总代价上常规分析并没有错，只是其推导出的总代价上界远大于实际可得的上界。其原因是这种分析法没界远大于实际可得的上界。其原因是这种分析法没有注意到连续的最坏情况删除是不可能的。有注意到连续的最坏情况删除是不可能的。 为了取得更准确的结果，还应该度量为了取得更准确的结果，还应该度量ADT数据数据结构的状态。对于每一个可能的状态结构的状态。对于每一个可能的状态S，赋予一个实，赋予一个实数数 (S)。 (S)称为称为S的的势能势能，其选择应使得，其选择应使得 (S)越高，越高，对处于对处于S状态的数据结构成功进行高代价操作的可能状态的数据结构成功进行高代价操作的可能越大。越大。 例如，将容器元素个数作为容器状态的势能就例如，将容器元素个数作为容器状态的势能就很合理，因为元素越多，对容器成功进行高代价操很合理，因为元素越多，对容器成功进行高代价操作的可能越大。作的可能越大。洒硷阅叭足君幕鞍喷椿钧靳药牌定征皱迁狰骏枚惋敞憋滋湃存厕泼诸役呼高级数据结构高级数据结构6JYP 考虑一个由考虑一个由m个对个对ADT操作的调用构成的序列，操作的调用构成的序列，并设并设ti是第是第i次调用的次调用的实际代价实际代价，定义第，定义第i次调用的次调用的分分摊代价摊代价ai为为ai = ti + (Si) (Si-1) Si-1是第是第i次调用开始前次调用开始前ADT数据结构的状态，数据结构的状态，Si是第是第i次调用结束后次调用结束后ADT数据结构的状态。设数据结构的状态。设 的选的选择使得择使得 (Sm) (S0)，则，则猩半索官晶犀剐译测泪蒲卸树闹终敷嘴稗卜郸壶菠著力谋委钢浇汝撮肋伸高级数据结构高级数据结构7JYP即，分摊代价的总和是实际代价总和的上界。即，分摊代价的总和是实际代价总和的上界。 例例1.12将容器元素个数作为将容器元素个数作为 (S)。若操作序列始。若操作序列始于空容器，则于空容器，则 (Sm) (S0)总是成立。下表反映了总是成立。下表反映了容器容器 (S)的典型变化情况。的典型变化情况。遇的么皖坡儡玛虹檬碴肖嗜匿焙绰少桓顶膝凭柳瑞点扬哪稽锐梆瑰议短坛高级数据结构高级数据结构8JYP 对对于于Add操操作作，ti=1， (Si) (Si-1)=1，所所以以ai=2；对对于于Delete操操作作，ti=k， (Si) (Si-1)= k，所以，所以ai=0。 任任何何一一个个调调用用Add操操作作 m1次次，Delete操操作作m2次次的的序列的总代价为序列的总代价为O(m1 2 + m2 0) = O(m1)。填酱鹊质益津令红页捂尺浊咕笑缝叠骨稻据附里打沫廊搂渣帖处仰志栗骇高级数据结构高级数据结构9JYP 可可见见，分分摊摊分分析析法法将将偶偶尔尔出出现现的的高高价价操操作作调调用用的的代价代价分摊分摊到邻近的其它调用上，故而得名。到邻近的其它调用上，故而得名。 而而且且，当当用用分分摊摊分分析析法法得得到到的的一一个个操操作作调调用用序序列列的的代代价价总总和和比比用用常常规规分分析析法法得得到到的的代代价价总总和和小小时时，人人们们就就得得到到了了更更接接近近实实际际代代价价的的分分析析结结果果，或或者者说说对算法时间复杂性的判断对算法时间复杂性的判断更准确更准确了。了。橇桑塌恋咨礁片垣悠痊颖还沪盟缩匝扦罕门滔舍追沈你嘴馈画啡材蛙慢浓高级数据结构高级数据结构10JYP两个字符串的最长公共子序列（两个字符串的最长公共子序列（2.4.3）一个字符串的子序列通过从字符串中删除零或多一个字符串的子序列通过从字符串中删除零或多个任意位置的字符得到。个任意位置的字符得到。两个字符串两个字符串x和和y的的最长公共子序列最长公共子序列记为记为lcs(x, y)。例如，例如，x = abdebcbb，y = adacbcb，则，则lcs(x, y)是是adcbb和和adbcb，如下所示：，如下所示： 祈恃益妊霜么筏热崎嘛悯甘荫传施陛饿祟羹腋辊讲牲梗尉斥拟寝堑漱上邑高级数据结构高级数据结构11JYP问题的基本求解方法问题的基本求解方法： 用用 标记空串，则标记空串，则lcs(x, )= lcs( , y) = 。 lcs(xa, ya) = lcs(x, y)a，即，即xa和和ya的最长公共子序的最长公共子序列由列由x和和y的最长公共子序列后接的最长公共子序列后接a构成。构成。 若若xa和和yb的最后一个字符不相等，则当的最后一个字符不相等，则当lcs(xa, yb)不以不以a结尾时一定等于结尾时一定等于lcs(x, yb)，当，当lcs(xa, yb)不不以以b结尾时一定等于结尾时一定等于lcs(xa, y)。因此。因此lcs(xa, yb)等于等于 lcs(x, yb)与与 lcs(xa, y)中较长者。中较长者。仇被届钢源蓉皮象醛玖袄堤讥过津孺辨挫争塌逞暇场吃狸坑笛擎特旨品攻高级数据结构高级数据结构12JYP 由此可得计算两个字符串最长公共子序列长度的由此可得计算两个字符串最长公共子序列长度的递归算法递归算法lcs: int String:lcs ( String y ) / 驱动器 int n = Length( ), m = y.Length( ); return lcs( n, m, y.str ); int String:lcs (int i, int j, char *y ) / 递归核心 if ( i = 0 | | j = 0) return 0; if ( stri-1 =yj-1 ) return ( lcs( i-1, j-1, y) + 1); return max( lcs( i-1, j, y), lcs( i, j-1, y); 球棚铡粥狼合祈揪轴圃猫纫睹沉峙筐绘偷赂扇砚靛酣孵皋襟酸葡孩嗽在挞高级数据结构高级数据结构13JYP 设设x的长度为的长度为n，y的长度为的长度为m，在最坏情况下，在最坏情况下lcs的时间复杂性为的时间复杂性为w(n, m)。w(n, m) = 因此，因此，w(n, m)2 w(n-1, m-1)2min(n, m) c，即，即lcs的时间复杂性是指数型的。的时间复杂性是指数型的。 进一步可发现，进一步可发现，lcs(i, 0)=0（0in），），lcs(0, j) =0（0jm）。）。lcs(i, j)的计算依赖于的计算依赖于lcs(i1, j1)、lcs(i1, j)和和lcs(i, j1)，如下图所示：，如下图所示： c （c为常数）为常数）n = 0或或m = 0w(n, m-1) + w(n-1, m)否则否则扒疙朝忆伯屉镇酣繁淳惭敦抖帐僻牡撰恬颐效匈杏珠破唾炬门障管神盖洱高级数据结构高级数据结构14JYP 根据以上拓扑关系，可以在不用递归的情况下计根据以上拓扑关系，可以在不用递归的情况下计算算lcs(i, j)。算法。算法Lcs实现了上述优化策略，这种策略实现了上述优化策略，这种策略体现了动态规划的思想。算法体现了动态规划的思想。算法Lcs的时间复杂性显然的时间复杂性显然是是O(n m)，这比其递归版有很大改进。，这比其递归版有很大改进。 上蓄度疙睛奶誊惹嗽他惕拓返鹊忘移骂晕咒箍空可游馅胺掇滩惑未戍玄撑高级数据结构高级数据结构15JYPint String:Lcs ( String y ) int n = Length( ), m = y.Length( ); int lcsMaxNMaxM; / MaxN和MaxM 是已定义的常数 int i, j; for ( i = 0; i = n; i+) lcsi0 = 0; / 初始值 for ( j = 0; j = m; j+) lcs0j = 0;/ 初始值 for ( i = 1; i = n; i+) for ( j = 1; j = m; j+) if ( stri-1 =y.strj-1 ) lcsij = lcsi-1j-1 + 1; else lcsij = max(lcsi-1j, lcsij-1); return lcsnm; 帆膀铜聋济钳烤提馈肺洗斯牛嚏步呐漫归明郁洗搅拳乃名撵腺驱伶笺泪印高级数据结构高级数据结构16JYP 例如，例如，x = abdebcbb，y = adacbcb，lcs(x, y) = adbcb，改，改进算法的计算如下所示：进算法的计算如下所示：70122234556012223444501222334440112223333011222222201122222210111111110000000000012345678吨春加扯孜瓜材供役皖拈慧符屯庐鹤嵌哈惜瓮洒忍志臆譬夏循寂合陈羡物高级数据结构高级数据结构17JYP机场模拟（机场模拟（2.9）计算机模拟（计算机模拟（simulation）：）：用软件模仿另一个系统的行为。用软件模仿另一个系统的行为。将研究对象表示为数据结构，对象动作表示为对将研究对象表示为数据结构，对象动作表示为对数据的操作，控制动作的规则转换为算法。数据的操作，控制动作的规则转换为算法。通过更改数据的值或改变算法设置，可以观察到通过更改数据的值或改变算法设置，可以观察到计算机模拟的变化，从而使用户能够推导出关于计算机模拟的变化，从而使用户能够推导出关于实际系统行为的有用结论。实际系统行为的有用结论。在计算机处理一个对象的动作期间，其它对象和在计算机处理一个对象的动作期间，其它对象和动作需等待。动作需等待。队列在计算机模拟中具有重要应用。队列在计算机模拟中具有重要应用。殉四铲赶唇素伊是暮韩箱球栏芥缺毛嚼萌卢菊停讼轧穿出翻灵弓软诸韧愈高级数据结构高级数据结构18JYP简单机场模拟：简单机场模拟：只有一个跑道。只有一个跑道。在每个时间单元，可起飞或降落一架飞机，但不在每个时间单元，可起飞或降落一架飞机，但不可同时起降。可同时起降。飞机准备降落或起飞的时间是随机的，在任一时飞机准备降落或起飞的时间是随机的，在任一时间单元，跑道可能处于空闲、降落或起飞状态，间单元，跑道可能处于空闲、降落或起飞状态，并且可能有一些飞机在等待降落或起飞。并且可能有一些飞机在等待降落或起飞。飞机在地上等待的代价比在空中等待的小，只有飞机在地上等待的代价比在空中等待的小，只有在没有飞机等待降落的情况下才允许飞机起飞。在没有飞机等待降落的情况下才允许飞机起飞。当出现队列满的情况时，则拒绝为新到达的飞机当出现队列满的情况时，则拒绝为新到达的飞机服务。服务。凶河逊制糟捐暴智蹈舍桌嗽疵熊对蘸靛世妥桂贞瑰捞承艺寺汛滞鱼牢量郝高级数据结构高级数据结构19JYP需要两个队列需要两个队列landing和和takeoff。飞机可描述为：飞机可描述为：struct plane int id;/ 编号 int tm;/ 到达队列时间;飞机的动作为：飞机的动作为：enum action ARRIVE, DEPART ;惟删邻收办痛贷递唤呜邑流纬粒惰累朋志验彻迎荆妈绝脐脯七冒输哦掇扛高级数据结构高级数据结构20JYP模拟运行模拟运行: : 时间单元时间单元:1 endtime，并产生关于机场行为的，并产生关于机场行为的重要统计信息，如处理的飞机数量，平均等待时重要统计信息，如处理的飞机数量，平均等待时间，被拒绝服务飞机的数量等。间，被拒绝服务飞机的数量等。 采用基于泊松分布的随机整数决定在每个时间单采用基于泊松分布的随机整数决定在每个时间单元有多少架新飞机需要降落或起飞。元有多少架新飞机需要降落或起飞。 假设在假设在10个时间单元中到达的飞机数分别是：个时间单元中到达的飞机数分别是：2，0，0，1，4，1，0，0，0，1，那么每个时间单元，那么每个时间单元的平均到达数是的平均到达数是0.9。楷史钻行剐替谷隆蜒履平豺快诗葛撤酮闪倡真肘应昼远河枯发栓察也垛荒高级数据结构高级数据结构21JYP 一个非负整数序列满足给定期望值一个非负整数序列满足给定期望值v v的泊松分布的泊松分布意味着，对于该序列的一段足够长的子序列，其意味着，对于该序列的一段足够长的子序列，其中整数的平均值接近中整数的平均值接近v v。 在模拟中还需要建立新到达飞机的数据，处理被在模拟中还需要建立新到达飞机的数据，处理被拒绝服务的飞机，起飞、降落飞机，处理机场空拒绝服务的飞机，起飞、降落飞机，处理机场空闲和总结模拟结果。闲和总结模拟结果。 下面是机场模拟类定义：下面是机场模拟类定义：捞爱潍斟卿礼俐暂由亦率变乐换虹坪姥上完炉冗餐蕊失哟兼掩渣阑痛演嘛高级数据结构高级数据结构22JYPclass AirportSimulation / 机场模拟。一个时间单元 = 起飞或降落的时间public: AirportSimulation( );/ 构造函数 void RunSimulation( );/ 模拟运行private: Queue landing(6); / 等待降落飞机队列，假设用环/ 型队列，实际长度为5 Queue takeoff(6); / 等待起飞飞机队列，同上 double expectarrive; /一个时间单元内期望到达降落飞机数 double expectdepart; /一个时间单元内期望到达起飞飞机数 int curtime;/ 当前时间 int endtime; / 模拟时间单元数 int idletime ; / 跑道空闲时间单元数 int landwait ; / 降落飞机的总等待时间诞刘厩营肘搽恐粗源骏溜漓青程哺近贩教块掏即委怒丘钒价喝烤梯会缴变高级数据结构高级数据结构23JYP int nland ; / 降落的飞机数 int nplanes; / 处理的飞机数 int nrefuse; / 拒绝服务的飞机数 int ntakeoff; / 起飞的飞机数 void Randomize( ); / 设置随机数种子 int PoissionRandom(double& expectvalue); / 根据泊松分布和给定期望值生成随机非负整数 plane* NewPlane(plane& p, action kind); / 建立新飞机的数据项 void Refuse(plane& p, action kind); / 拒绝服务 void Land(plane& p); / 降落飞机 void Fly(plane& p); / 起飞飞机 void Idle( ); / 处理空闲时间单元 void Conclude( ); / 总结模拟结果;京钱馆董闽头补禾扯惑浙剃眩顽拢吊顶纤攀纫装道睡固匡泉蛋线卷坏匀侍高级数据结构高级数据结构24JYP 构造函数初始化各变量，如下所示：构造函数初始化各变量，如下所示：AirportSimulation:AirportSimulation( ) / 构造函数 Boolean ok; cout endtime; idletime = landwait = nland = nplanes = 0; nrefuse = ntakeoff = takoffwait = 0; / 初值 Randomize( ); / 设置随机数种子 do cout expectarrive; cout expectdepart;物常渺暂辱予桥斥匣拒沥牺含冲灯茸倪岂驳自喳媚弧除藤淋并卞敞温坛玫高级数据结构高级数据结构25JYP if (expectarrive 0.0 | expectdepart 0.0) cout “这些数不能为负！请重新输入。” 1.0) cout “机场将饱和！请重新输入。” endl; ok = FALSE; else ok = TRUE; while (ok = FALSE);到滚卸芍魂烫颇坦豹霸铸男绅晓萝忆潞过伪缎烛胶徽躲鞠价幅汞湘稽淋催高级数据结构高级数据结构26JYP RunSimulation( )是模拟运行的主控程序：是模拟运行的主控程序：void AirportSimulation:RunSimulation( ) int pri; / 伪随机整数 plane p; for (curtime = 1; curtime = endtime; curtime+) cout “时间单元” curtime “：” ; pri = PoissionRandom(expectarrive); for (int i =1; i = pri; i+) /处理新到达准备降落的飞机 p = *NewPlane(p, ARRIVE); if (landing.IsFull( ) Refuse(p, ARRIVE); else landing.Add(p); pri = PoissionRandom(expectdepart);铡坠靛抿招仟矢抚狮塞挤乓暴罚硬怖袜郊契戚笆酸井挠糯悸隘解峦攻盘昼高级数据结构高级数据结构27JYP for (int i =1; i limit) n+; x *= rand( ) / (double) INT_MAX; return n; 惧拯底孝匪编啃灾勤搔溶蓉钟纂阵寞繁陶器渺揍说戏咕件疟庐卞疵百躯尘高级数据结构高级数据结构30JYP 建立新飞机的数据项由函数建立新飞机的数据项由函数NewPlane实现：实现：plane* AirportSimulation:NewPlane(plane& p, action kind) nplanes+; / 飞机总数加1 p.id = nplanes; p.tm = curtime; switch (kind) case ARRIVE: cout “飞机” nplanes “准备降落。” endl; break; case DEPART: cout “飞机” nplanes “准备起飞。” endl; break; return &p;蒸玫下斑碉蝉掌袖贿霹嚼摔叠脸贼筏赡霍廷批最槽朝箱平圾廉重诽畴灶畏高级数据结构高级数据结构31JYP 处理被拒绝的飞机由函数处理被拒绝的飞机由函数Refuse实现实现:void AirportSimulation:Refuse(plane& p, action kind) switch (kind) case ARRIVE: cout “引导飞机” p.id “到其它机场降落。” endl; break; case DEPART: cout “告诉飞机” p.id “等一会儿再试。” endl; break; nrefuse+; / 被拒绝飞机总数加1桑褐戴缀底滞户贮稿少呛认棱嘶枣卑错抓哟容饥橡废棘默撇矾擅黎度搞厩高级数据结构高级数据结构32JYP 处理飞机降落由函数处理飞机降落由函数Land实现：实现：void AirportSimulation:Land(plane& p) int wait; wait = curtime p.tm; cout “飞机” p.id “降落，该机等待时间：” wait “。” endl; nland+;/ 降落飞机总数加1 landwait += wait;/ 累加总降落等待时间抨咎出并逮恢描击孔想恶做钝森辈磊赡记答辟舱膊咬愚赂避兆贯星惶葫左高级数据结构高级数据结构33JYP 处理飞机起飞由函数处理飞机起飞由函数Fly实现：实现：void AirportSimulation:Fly(plane& p) int wait = curtime p.tm; cout “飞机” p.id “起飞，该机等待时间：” wait “。” endl; ntakeoff+;/ 起飞飞机总数加1 takeoffwait += wait;/ 累加总起飞等待时间漆元馏嫌挪唾响唱妄赎峨帅帝茹浦将黔缺惦肛孪崇演印汲突撼详梆诸酣坐高级数据结构高级数据结构34JYP 处理机场空闲由函数处理机场空闲由函数Idle实现：实现：void AirportSimulation:Idle( ) cout “跑道空闲。” endl; idletime+;/ 跑道空闲时间加1 总结模拟结果由函数总结模拟结果由函数Conclude实现：实现：void AirportSimulation:Conclude( ) cout “总模拟时间单元数：” endtime endl; cout “总共处理的飞机数：” nplanes endl; cout “降落飞机总数：” nland endl; cout “起飞飞机总数：” ntakeoff endl;臆稗扶柱唯竭跳刮挖柯靴雅撅都涯济莫哟确星龟某椰波韧尺塑淀宪涣娃磁高级数据结构高级数据结构35JYP cout “拒绝服务的飞机总数：” nrefuse endl; cout “队列中剩余的准备降落飞机数：” landing.Size( ) endl; / 假设队列成员函数Size( )返回队列中元素个数 cout “队列中剩余的准备起飞飞机数：” takeoff.Size( ) 0) cout “跑道空闲时间百分比：” (double) idletime / endtime) * 100.0 0) cout “降落平均等待时间：” (double) landwait / nland 0) cout “起飞平均等待时间：” (double) takeoffwait / ntakeoff endl;晰顿保椅淆处泡姆为寺晦蓑蜘例胀守尸瘤滞弊融毅抹划处禽骤椽患声润趴高级数据结构高级数据结构36JYP可通过下列程序模拟运行：可通过下列程序模拟运行：#include “common.h”#include “simdefs.h” / 存放模拟类定义及相关函数实现void main( ) AirportSimulation s; s.RunSimulation( );家壳纲杭勃袜消紧泻殷樱撒翱舌血皱苍傀蓑昭辖求吧季甄盗稗良晕眶仲满高级数据结构高级数据结构37JYP模拟过程产生的数据如下：模拟过程产生的数据如下：请输入模拟时间单元数：请输入模拟时间单元数：30请输入一个时间单元内期望到达降落飞机数：请输入一个时间单元内期望到达降落飞机数：0.47请输入一个时间单元内期望到达起飞飞机数：请输入一个时间单元内期望到达起飞飞机数：0.47时间单元时间单元1：飞机：飞机1准备降落。准备降落。 飞机飞机1降落，该机等待时间：降落，该机等待时间：0。时间单元时间单元2：跑道空闲。：跑道空闲。时间单元时间单元3：飞机：飞机2准备降落。准备降落。 飞机飞机3准备降落。准备降落。 飞机飞机2降落，该机等待时间：降落，该机等待时间：0。时间单元时间单元4： 飞机飞机3降落，该机等待时间：降落，该机等待时间：1。怠确坡幅搅匙伶迂翱通舟糖椽车氓撇演汀效妥瞥斑乞野庆虞幽孜怀低稽禄高级数据结构高级数据结构38JYP时间单元时间单元5：飞机：飞机4准备降落。准备降落。 飞机飞机5准备降落。准备降落。 飞机飞机6准备起飞。准备起飞。 飞机飞机7准备起飞。准备起飞。 飞机飞机4降落，该机等待时间：降落，该机等待时间：0。时间单元时间单元6：飞机：飞机8准备起飞。准备起飞。 飞机飞机5降落，该机等待时间：降落，该机等待时间：1。时间单元时间单元7：飞机：飞机9准备起飞。准备起飞。 飞机飞机10准备起飞。准备起飞。 飞机飞机6起飞，该机等待时间：起飞，该机等待时间：2。时间单元时间单元8： 飞机飞机7起飞，该机等待时间：起飞，该机等待时间：3。时间单元时间单元9： 飞机飞机8起飞，该机等待时间：起飞，该机等待时间：3。霄完最矽钱蔫圈逊滚揉饿纪史誊蘸回湾肄胆朵冰插业苑锦姑倦呆裙佃董准高级数据结构高级数据结构39JYP时间单元时间单元10：飞机：飞机11准备降落。准备降落。 飞机飞机11降落，该机等待时间：降落，该机等待时间：0。时间单元时间单元11：飞机：飞机12准备起飞。准备起飞。 飞机飞机9起飞，该机等待时间：起飞，该机等待时间：4。时间单元时间单元12：飞机：飞机13准备降落。准备降落。 飞机飞机14准备降落。准备降落。 飞机飞机13降落，该机等待时间：降落，该机等待时间：0。时间单元时间单元13： 飞机飞机14降落，该机等待时间：降落，该机等待时间：1。时间单元时间单元14： 飞机飞机10起飞，该机等待时间：起飞，该机等待时间：7。时间单元时间单元15： 飞机飞机15准备降落。准备降落。 飞机飞机16准备起飞。准备起飞。 飞机飞机17准备起飞。准备起飞。 飞机飞机15降落，该机等待时间：降落，该机等待时间：0。养斌烦窗王啥炎壬轿护兵国赛豺涨契甄喻罚伯惜伤遏保赦拎寅瑚台捍蹈咐高级数据结构高级数据结构40JYP时间单元时间单元16：飞机：飞机18准备降落。准备降落。 飞机飞机19准备降落。准备降落。 飞机飞机20准备起飞。准备起飞。 飞机飞机21准备起飞。准备起飞。 飞机飞机18降落，该机等待时间：降落，该机等待时间：0。时间单元时间单元17： 飞机飞机22准备降落。准备降落。 飞机飞机19降落，该机等待时间：降落，该机等待时间：1。时间单元时间单元18： 飞机飞机23准备起飞。准备起飞。 告诉飞机告诉飞机23等一会儿再试。等一会儿再试。 飞机飞机22降落，该机等待时间：降落，该机等待时间：1。藉华蒜咕廉狐魂襄眨父罪昌名脯勿仔壹慈蛆贱卢恒探洒挥滑丙咎私孺矛谱高级数据结构高级数据结构41JYP时间单元时间单元19： 飞机飞机24准备降落。准备降落。 飞机飞机25准备降落。准备降落。 飞机飞机26准备降落。准备降落。 飞机飞机27准备起飞。准备起飞。 告诉飞机告诉飞机27等一会儿再试。等一会儿再试。 飞机飞机24降落，该机等待时间：降落，该机等待时间：0。时间单元时间单元20： 飞机飞机28准备降落。准备降落。 飞机飞机29准备降落。准备降落。 飞机飞机30准备降落。准备降落。 飞机飞机31准备降落。准备降落。 引导飞机引导飞机31到其它机场降落。到其它机场降落。 飞机飞机25降落，该机等待时间：降落，该机等待时间：1。典础嗣谍坦像衫槐郊训企聂蛰图甲吕七讫粉滚兰篱断牙八莱焕肮付玻娠尸高级数据结构高级数据结构42JYP时间单元时间单元21：飞机：飞机32准备降落。准备降落。 飞机飞机33准备起飞。准备起飞。 告诉飞机告诉飞机33等一会儿再试。等一会儿再试。 飞机飞机26降落，该机等待时间：降落，该机等待时间：2。时间单元时间单元22：飞机：飞机28降落，该机等待时间：降落，该机等待时间：2。时间单元时间单元23：飞机：飞机29降落，该机等待时间：降落，该机等待时间：3。时间单元时间单元24：飞机：飞机34准备起飞。准备起飞。 告诉飞机告诉飞机34等一会儿再试。等一会儿再试。 飞机飞机30降落，该机等待时间：降落，该机等待时间：4。咸畸谓奏摈谢骆躺衅候泛狈示嘻频蛔燃咒蛤其箩得佩贤能付齐找捆妓泞讹高级数据结构高级数据结构43JYP时间单元时间单元25：飞机：飞机35准备起飞。准备起飞。 告诉飞机告诉飞机35等一会儿再试。等一会儿再试。 飞机飞机36准备起飞。准备起飞。 告诉飞机告诉飞机36等一会儿再试。等一会儿再试。 飞机飞机32降落，该机等待时间：降落，该机等待时间：4。时间单元时间单元26：飞机：飞机37准备起飞。准备起飞。 告诉飞机告诉飞机37等一会儿再试。等一会儿再试。 飞机飞机12起飞，该机等待时间：起飞，该机等待时间：15。时间单元时间单元27：飞机：飞机16起飞，该机等待时间：起飞，该机等待时间：12。时间单元时间单元28：飞机：飞机17起飞，该机等待时间：起飞，该机等待时间：13。时间单元时间单元29：飞机：飞机20起飞，该机等待时间：起飞，该机等待时间：13。傻拾巍郭言老滇跳募瞒爪邦臼集偏匪木徒槽滔篮浚克垮灸辗聘炎革锌台夸高级数据结构高级数据结构44JYP时间单元时间单元30：飞机：飞机38准备起飞。准备起飞。 飞机飞机21起飞，该机等待时间：起飞，该机等待时间：14。总模拟时间单元数：总模拟时间单元数：30总共处理的飞机数：总共处理的飞机数：38降落飞机总数：降落飞机总数：19起飞飞机总数：起飞飞机总数：10拒绝服务的飞机总数：拒绝服务的飞机总数：8队列中剩余的准备降落飞机数：队列中剩余的准备降落飞机数：0 队列中剩余的准备起飞飞机数：队列中剩余的准备起飞飞机数：1跑道空闲时间百分比：跑道空闲时间百分比：3.33降落平均等待时间：降落平均等待时间：1.11起飞平均等待时间：起飞平均等待时间：8.60菌猪制音躯匿漱刘弊胁氟雍炉撤信侠脏适米销磨守瞳缘丽画翰徘册届稼吵高级数据结构高级数据结构45JYP二叉树计数二叉树计数(4.9) 当当n = 0或或1时，只有一棵二叉树。时，只有一棵二叉树。 当当n = 2，存在，存在2棵不同（结构）的二叉树：棵不同（结构）的二叉树： 侗旋件捞橡虱患怕贵氧催蹭倒倦裹述痔林圾忧庙饺那撮洱迫尾承椽薛溶诡高级数据结构高级数据结构46JYP 而当而当n = 3，则存在，则存在5棵不同的二叉树：棵不同的二叉树：那么，具有那么，具有n个结点的不同二叉树究竟有多少呢？个结点的不同二叉树究竟有多少呢？风俄尹步浊兰杰峰蒂筛蓝店亏虏筹向切归菇圆怨晾想段垣裕坐利饶六尿府高级数据结构高级数据结构47JYP 不不失失一一般般性性，将将树树的的n个个结结点点编编号号为为1到到n。假假设设一一棵棵二二叉叉树树的的前前序序序序列列为为1 2 3 4 5 6 7 8 9且且其其中中序序序序列列为为2 3 1 5 4 7 8 6 9，则则通通过过这这对对序序列列可可以以唯唯一一确确定定一棵二叉树。一棵二叉树。 为为了了构构造造相相应应的的二二叉叉树树，可可找找出出前前序序第第一一个个结结点点，即即1。于于是是，结结点点1是是树树根根，中中序序序序列列中中所所有有在在1之之前前的的结结点点（2 3）属属于于左左子子树树，其其余余结结点点（5 4 7 8 6 9）属于右子树。属于右子树。稍田郎灭颂籍响柏吸稽砧邑彻厄饮圣苯硕忱参骚揭屎讽抉吩欠阁尸彤黑租高级数据结构高级数据结构48JYP 这一步构造如下所示：这一步构造如下所示：虾澄搓娜与抉亮枕沉摹汐马稠弃区涪池团丰特借孰勇量辐缠袋轴谢兰冈腰高级数据结构高级数据结构49JYP 接接着着，可可根根据据前前序序序序列列2 3和和中中序序序序列列2 3构构造造左左子子树树。显显然然，结结点点2是是树树根根。由由于于在在中中序序序序列列中中，结结点点2之之前前无无结结点点，所所以以其其左左子子树树为为空空，结结点点3是是其其右右子子树，如下图所示：树，如下图所示： 抢勿扔善肾盛逻藻径无一袁丧酋磺倦锗刚琴踢歼怀践腐距正媳唇凛刚宙吹高级数据结构高级数据结构50JYP 如此继续，最终可唯一地构造下图所示的二叉树：如此继续，最终可唯一地构造下图所示的二叉树：膨酬撩佃末敬走锈焉炮门扮趋碟刊讨屁适沂烃虐免氧间蜒脱赶童依敢共韭高级数据结构高级数据结构51JYP 一一般般地地，我我们们可可以以设设计计算算法法，根根据据二二叉叉树树的的前前序序/中序序列对构造该树。中序序列对构造该树。 可可以以证证明明，每每一一棵棵二二叉叉树树都都有有唯唯一一的的前前序序/中中序序序序列对。列对。 如如果果树树中中结结点点按按前前序序编编号号，即即树树的的前前序序序序列列为为1, 2, , n，则则由由上上讨讨论论可可知知，不不同同的的二二叉叉树树定定义义不不同同的中序序列。的中序序列。 因因此此，不不同同的的二二叉叉树树个个数数等等于于从从前前序序序序列列为为1, 2, , n的二叉树可产生的不同的中序序列的个数。的二叉树可产生的不同的中序序列的个数。筷术蹦雅陀晨越葬乔大莱睛叫且贡温犀讥骨仕肆线狼拐酪诊蚕粘蕾朴暇墩高级数据结构高级数据结构52JYP 设设bn是是具具有有n个个结结点点的的不不同同二二叉叉树树的的个个数数。bn实实际际上上是是按按以以下下方方式式形形成成的的各各种种可可能能的的二二叉叉树树个个数数之之和和：一一个个根根和和两两个个结结点点数数分分别别为为i和和ni1的的子子树树(0i n)，如下所示：，如下所示：襄抨最敛瓦阀棱声孩淬棍患番奢噎誓付俞姨朴崇磁捡箱众魂甘捡练球轨截高级数据结构高级数据结构53JYP 对于每一个对于每一个i，存在，存在bi bn-i-1棵不同的树，因此有棵不同的树，因此有(4.3) 为了用为了用n表示表示bn，必须求解递归方程，必须求解递归方程(4.3)。设。设(4.4)邦冶喧踌林上婿拙谨烁因惰裕痕意换姥疚鬃轧盼杰蓄惭垢趴川彤色宏怂甄高级数据结构高级数据结构54JYP B(x)是二叉树个数的生成函数。由于是二叉树个数的生成函数。由于 毫步叛戒扳棠庞炸足扣饵读隙洋江绩曝咎午皱灶记韭全恫嚣步羌跺木送掘高级数据结构高级数据结构55JYP即即 x B2(x) B(x) + 1 = 0寇样段级陷汤疏灼蠕摊铰案皑护惯鄙率颁培锗抑度歉汕酮他蔚扭茸摘坊撰高级数据结构高级数据结构56JYP 解解此此一一元元二二次次方方程程，并并注注意意B(0) = b0 = 1（等等式式(4.3)），可得），可得 利用二项式公式展开利用二项式公式展开(1 4x)1/2得到得到然哟秃御悉婚坟社馏辑吱史渣躇宛秘匹芯救侍风峰臻遥詹示醉笛容奸耳根高级数据结构高级数据结构57JYP 令令n = m + 1，可得，可得(4.5)卉缄疆砧婿疾扒佃羹蒜仙佑碘吻志蹋例胺搏母炔衅火纺没狐俯抉完赊疽舷高级数据结构高级数据结构58JYP 比比较较等等式式(4.4) 和和(4.5)，并并注注意意bn是是B(x)中中xn的的系数，可得系数，可得柒翻卫竣革盏峪籍揣罢钒茹越隋呆桓鸥范沏嘿熊疮憎柔蒋湿蛰闻澄雇奢钥高级数据结构高级数据结构59JYP赔兽惟魄星卧菜晓刷利钩荐秒旦藐职完榷果辗欠灰哟捷谭羡郭忱块耳治裕高级数据结构高级数据结构60JYP最小最大堆最小最大堆 (5.2)5.2.1 双端优先队列与最小最大堆双端优先队列与最小最大堆 双端优先队列双端优先队列是一种支持下列操作的数据结构：是一种支持下列操作的数据结构：（1） 插入一个具有任意插入一个具有任意key值的元素值的元素（2） 删除删除key值最大的元素值最大的元素（3） 删除删除key值最小的元素值最小的元素 当只需要支持两个删除操作之一时，可采用前一当只需要支持两个删除操作之一时，可采用前一节的最小堆或最大堆。而节的最小堆或最大堆。而最小最大堆最小最大堆可支持以上全可支持以上全部操作。部操作。仑泻颜弯嘲傀躁凹挛扛拙噪嘶盐悬华己步喀挟猫浓譬邻误猛脆爆盛钦坦元高级数据结构高级数据结构61JYP 双端优先队列可定义为如下的抽象类：双端优先队列可定义为如下的抽象类：template class DEPQ public: virtual void Insert(const Element&) = 0; virtual Element* DeleteMax(Element&) = 0; virtual Element* DeleteMin(Element&) = 0;其中，假设其中，假设Element含有一个含有一个key数据成员。数据成员。踊受蹄匀朔析橡官讯网渺宗国擅梅炼妒坊理豫支向袁筋宵掏琵权唬胯灿帐高级数据结构高级数据结构62JYP 定义：最小最大堆定义：最小最大堆是一棵完全二叉树，且其中每是一棵完全二叉树，且其中每个元素有一个个元素有一个key数据成员。树的各层交替为最小层数据成员。树的各层交替为最小层和最大层。根结点在最小层。设和最大层。根结点在最小层。设x是最小最大堆的任是最小最大堆的任意结点。若意结点。若x在最小（最大）层上，则在最小（最大）层上，则x中的元素的中的元素的key值在以值在以x为根的子树的所有元素中是最小（最大）为根的子树的所有元素中是最小（最大）的。位于最小（最大）层的结点称为的。位于最小（最大）层的结点称为最小（最大）最小（最大）结点结点。幸土竖罚结秩碍态软切柠瞬歇酌喇质盗财魁额镶恶俺帛己蹈丈震言旁蛛缺高级数据结构高级数据结构63JYP 下面是一个具有下面是一个具有12个元素的最小最大堆，其中最个元素的最小最大堆，其中最大层的结点用粗体字表示：大层的结点用粗体字表示：萄贿部蛙疏填叙钝别朝颁免赖祁纶摇滁敌云除判炔酞饼况默趟洱柏桂析筏高级数据结构高级数据结构64JYP 最小最大堆定义为最小最大堆定义为DEPQ的派生类，以确保实现的派生类，以确保实现DEPQ的三个操作。的三个操作。template class MinMaxHeap: public DEPQ public: MinMaxHeap (const int); / 构造函数 MinMaxHeap ( ); / 析构函数 void Insert (const Element&); Element* DeleteMax(Element& x ); Element* DeleteMin(Element& x );private: Element *h; int n; / 最小最大堆的当前元素个数 int MaxSize;/ 堆中可容纳元素的最大个数鱼惋宿誊潍认淳捉坟劣虫架携美斗冠街虎敬诲隔矩燕忆萨拾幂寨廓痹纺醚高级数据结构高级数据结构65JYP / 其它用于实现最小最大堆的私有数据成员 ;template / 构造函数定义MinMaxHeap:MinMaxHeap (const int sz = DefaultHeapSize) : MaxSize(sz), n(0) h = new ElementMaxSize+1; / h0 不用印对胞正笺酱裤协婚痰痞滇森群舵骑鲤填目溯纵诣兼毋货呵使枕椅泽具兄高级数据结构高级数据结构66JYP5.2.2 插入操作插入操作 假假设设将将key为为5的的元元素素插插入入图图5.4的的最最小小最最大大堆堆。插插入后的堆有入后的堆有13个元素，其形状如下图：个元素，其形状如下图：断嫌作鳃敞辊改旷觉坠卯矾郁症理豢一软斩炭唤街饱认矗奶擞尝架瑟摆殴高级数据结构高级数据结构67JYP 最小最大堆的插入算法也需要沿从新结点最小最大堆的插入算法也需要沿从新结点j到根到根的路径比较的路径比较key值。值。 比较结点比较结点j的的key值值5和和j的双亲的的双亲的key值值10，由于存，由于存放放key值值10的结点位于最小层，且的结点位于最小层，且5 10，所以，所以5一定一定小于所有从小于所有从j到根的路径中位于最大层的结点的到根的路径中位于最大层的结点的key值。值。 为了保持最小最大堆的性质，只需要检查从为了保持最小最大堆的性质，只需要检查从j到到根的路径中的最小结点即可。首先，将根的路径中的最小结点即可。首先，将key为为10的元的元素移到结点素移到结点j。接着，将。接着，将key为为7的元素移到的元素移到10的原来的原来位置。最后，将位置。最后，将key为为5的元素插入根结点。的元素插入根结点。婿兵握汁忿装汹叼煌耘豁煽坟慕琴监围潍班驮才氦坯封碾性税铸烩捅草咆高级数据结构高级数据结构68JYP 由此形成的最小最大堆如下图，圆周加粗的结点由此形成的最小最大堆如下图，圆周加粗的结点内容在插入过程修改过：内容在插入过程修改过：娇犁癣掩吐荐咆虾快徐祥重酬芽赵萌厌潭盟椅执狭薛菱酝瞎彦现斤搔废食高级数据结构高级数据结构69JYP 再假设将再假设将key为为80的元素插入图的元素插入图5.4所示的最小最所示的最小最大堆。插入后的堆有大堆。插入后的堆有13个元素，其形状也与前面相个元素，其形状也与前面相同。同。 由于存放由于存放key值值10的结点位于最小层，且的结点位于最小层，且10 80，所以，所以80一定大于所有从一定大于所有从j到根的路径中位于最小层到根的路径中位于最小层的结点的的结点的key值。值。 为了保持最小最大堆的性质，只需要检查从为了保持最小最大堆的性质，只需要检查从j到到根的路径中的最大结点即可。图根的路径中的最大结点即可。图5.4中只有一个这样中只有一个这样的结点，其元素的的结点，其元素的key值为值为40，将该元素移到结点，将该元素移到结点j，并将，并将key为为80的新元素插入的新元素插入key为为40的元素原来的的元素原来的结点。结点。音豺釉嚣站炎周庭江捞味乾迎愚徐继刨蔓自忻损家拥卿迟胎炒儡践卒尸诞高级数据结构高级数据结构70JYP 由此形成的最小最大堆如下图：由此形成的最小最大堆如下图：芭裁蛾查讥硒驭灌虐拼彻靠凤圣圈酥贪南抖凭砒踏料谈探感气辩板房怠豆高级数据结构高级数据结构71JYP 成员函数成员函数Insert实现了上述过程，其中又用到私实现了上述过程，其中又用到私有成员函数有成员函数VerifyMax，VerifyMin 和和level。template void MinMaxHeap:Insert(const Element&x ) if (n = MaxSize ) MinMaxFull( ); return; n+; int p = n/2; / p是新结点的双亲 if (!p) h1 = x; return; / 插入初始时为空的堆 switch (level(p) case MIN: if (x.key hp.key) / 沿着最大层检查 hn=hp; VerifyMax(p, x); else VerifyMin(n, x); / 沿着最小层检查 / switch结束 / Insert结束 搏括奢勘嗣镊会亩彭窃彼音币别践蹄室函卯贝矗步拘倚郧甘勉劫盒鲍仍义高级数据结构高级数据结构73JYP 函数函数level确定一个结点是位于最小最大堆的最小确定一个结点是位于最小最大堆的最小层，还是位于最大层。根据引理层，还是位于最大层。根据引理4.2，当，当 log2(j + 1) 为偶数时，结点为偶数时，结点j位于最大层，否则位于最小层。位于最大层，否则位于最小层。 函数函数VerifyMax从最大结点从最大结点i开始，沿着从结点开始，沿着从结点i到到最小最大堆的根的路径检查最大结点，查找插入元最小最大堆的根的路径检查最大结点，查找插入元素素x的正确结点。在查找过程中，的正确结点。在查找过程中，key值小于值小于x.key的的元素被移到下一个最大层。元素被移到下一个最大层。熟龟谅颓夏立勒乓室挣毯耕忿渣出钦犊收酣仓薯诗嚎糕紫哩塞澳羌顷灵简高级数据结构高级数据结构74JYPtemplate void MinMaxHeap:VerifyMax (int i, const Element&x ) / 沿着从最大结点i / 到根结点的路径检查最大结点，将x插入正确位置 for (int gp = i/4; gp & (x.key hgp.key); gp /=4) / gp是 i的祖父 hi = hgp;/ 将hgp移到hi i = gp; hi = x; / 将x插入结点i 象穴喳贺侣滚泉蓑链自卵粘己作眉歹藐脚卢息吼晒瞳挝儒椒捂亢辙宪缀嘲高级数据结构高级数据结构75JYP 函数函数VerifyMin与与VerifyMax类似，所不同的是，类似，所不同的是，前者从最小结点前者从最小结点i开始，沿着从结点开始，沿着从结点i到根的路径检查到根的路径检查最小结点，将元素最小结点，将元素x插入正确位置。插入正确位置。 分析：分析：由于由于n个元素的最小最大堆有个元素的最小最大堆有O(log n)层，层，成员函数成员函数Insert的时间复杂性是的时间复杂性是O(log n)。箍鲤渭靠例价舆鲁南鹃煮佃喀令蒋丙翁鼻迢探健须篱亢纷聪岳嘎份裸阎赘高级数据结构高级数据结构76JYP5.2.3 删除最小元素操作删除最小元素操作 最小最大堆中删除最小元素在根结点中。删除图最小最大堆中删除最小元素在根结点中。删除图5.4的最小元素的最小元素7之后的堆有之后的堆有11个元素，形状如下：个元素，形状如下：至胰丧觅惜龙怖劫吮砷庇比亨弗隆妈痹学喳森逞恬痈获捡编沾骨妓尔阉堕高级数据结构高级数据结构77JYP 此时应将此时应将key值为值为12的元素从堆中删除后再重新的元素从堆中删除后再重新插入，需要沿着从根到叶的路径检查相关结点。插入，需要沿着从根到叶的路径检查相关结点。 一般而言，将元素一般而言，将元素x插入根结点为空的最小最大插入根结点为空的最小最大堆堆h中有两种情况需要考虑：中有两种情况需要考虑：（1） 根结点无子女，这时可将根结点无子女，这时可将x插入根结点中。插入根结点中。（2） 根结点至少有一个子女。这时堆中的最小元根结点至少有一个子女。这时堆中的最小元素（不算元素素（不算元素x）位于根结点的子女结点或孙子女结）位于根结点的子女结点或孙子女结点（最多点（最多6个）之一。假设该结点的编号为个）之一。假设该结点的编号为k，则还，则还需要考虑下列可能性：需要考虑下列可能性： (a) x.keyhk.key。由于。由于h中不存在比中不存在比x更小的更小的元素，所以元素，所以x可插入根。可插入根。冗昭霉虽畔艘巡蘑柯拓株秧忌翁朽卉均苟奸睛犊瞪你乾援莆陶项勋阀梅则高级数据结构高级数据结构78JYP (b) x.key hk.key且且k是根的子女。由于是根的子女。由于k是是最大结点，其后代的最大结点，其后代的key值都不大于值都不大于hk.key，因而，因而也不大于也不大于x.key。所以可将元素。所以可将元素hk移到根，并将元移到根，并将元素素x插入结点插入结点k。 (c) x.key hk.key且且k是根的孙子女。这时也是根的孙子女。这时也可将元素可将元素hk移到根。设移到根。设p是是k的双亲。若的双亲。若x.key hp.key，则将，则将x 和和hp交换。这时，问题转化为将交换。这时，问题转化为将x插入以插入以k为根的子堆中，且为根的子堆中，且hk已腾空。这与初始已腾空。这与初始插入根结点为空的最小最大堆插入根结点为空的最小最大堆h的情形类似。的情形类似。抚遏占粟纵赁善悔肄呸稠噪等看羌器篮顾裴盾蔓茫诞肥凶革坦纹的我晕便高级数据结构高级数据结构79JYP 在在本本例例中中，x.key = 12，根根结结点点的的子子女女结结点点或或孙孙子子女女结点中的最小元素的结点中的最小元素的key值为值为9。 设设k为该结点编号，为该结点编号，p是是k的双亲。的双亲。 由由于于12 9且且k是是根根的的孙孙子子女女，这这属属于于情情形形2(c)。因因此此，将将key值值为为9的的元元素素（即即hk）移移到到根根结结点点。由由于于x.key = 12 70 = hp.key，所以不将，所以不将x 和和hp交换。交换。 这时的情形如下一页所示。这时的情形如下一页所示。囱鼓娥嘲闽翻剪漱郭俊插腐娘集辙厅贞在禹稽忙眷曹哺嚏畸长善华依坯诡高级数据结构高级数据结构80JYP现现在在，需需要要将将x插插入入以以k为为根根的的子子堆堆中中。结结点点k的的子子女女结结点点或或孙孙子子女女结结点点中中的的最最小小元元素素的的key值值为为20。由由于于12 20，这属于情形，这属于情形2(a)，因此可将，因此可将x插入插入hk。范冈抓橙嗜摹救丑违敛捐郁笛检争林延蕊酪哼黍贿跑斌剥俏楼氯骄捞图缅高级数据结构高级数据结构81JYP 通过以上讨论，可得成员函数通过以上讨论，可得成员函数DeleteMin。template Element* MinMaxHeap: DeleteMin(Element&y) / 从最小最大堆中删除并返回最小元素 if (!n) MinMaxEmpty( ); return 0; y = h1; / 保存根元素 Element x = hn-; int i = 1, j = n/2; / 为重新插入x作初始化 / 寻找插入x的位置 while (i = j) / i 有子女，情况(2) int k = MinChildGrandChild(i); if (x.key = hk.key) break;/ 情况 2(a)，可将x 插入hi左奉瞎露想南碌拘蒙嚣均畴吵锚挫彰恐寿碌崇帕提狞窄嘱谆糜睛雅唾温袋高级数据结构高级数据结构82JYP else / 情况2(b) 或 (c) hi = hk; if (k hp.key) Element t = hp; hp = x; x = t; / if (k=2*i+1)结束 i = k; / if (x.key 1），最小元素在最小堆的根结点中，最大元素在最），最小元素在最小堆的根结点中，最大元素在最大堆的根结点中。若大堆的根结点中。若n = 1，则最小和最大元素相同，则最小和最大元素相同，在最小堆的根结点中。在最小堆的根结点中。脉痞猖硒碱拘悉肩食抹载奴歉凿坚罐截屏寥重丝巨骡叉揖视阶掘刻蚂肠熔高级数据结构高级数据结构89JYP 若若i是最小堆中的结点，则其在最大堆中的对应结是最小堆中的结点，则其在最大堆中的对应结点是点是i + 2 log2i -1。因此，双堆定义性质（。因此，双堆定义性质（4）中的）中的j可如下确定：可如下确定：j = i + 2log2i -1;if (j n + 1) j /= 2; 注意，如果最小堆的所有叶结点都满足性质注意，如果最小堆的所有叶结点都满足性质（4），则最小堆中其余结点也满足性质（），则最小堆中其余结点也满足性质（4）。）。肉恫名挤棍控蛤属钒隐贬奸贯贮之蜜嚏茶膨乎灼记逢尚凶洒岗泅颗朱桌哗高级数据结构高级数据结构90JYP 双堆双堆Deap的类定义如下：的类定义如下：template class Deap: public DEPQ public: Deap (const int); Deap ( ); void Insert (const Element&); Element* DeleteMax(Element& ); Element* DeleteMin(Element& );private: Element *d; int n; / 当前元素个数 int MaxSize;/ 可容纳的最大元素个数 / 其它私有数据成员灵油絮纠扎百况撬碧赌胖廓诞慨运暂荡着园琐购案叁磐醒我扶岂娟洁拇撂高级数据结构高级数据结构91JYP ;template Deap :Deap (const int sz = DefaultHeapSize):MaxSize(sz), n(0) d = new ElementMaxSize+2; / d0 和d1不用甭卤毡朋喂岛瓢茂撒脚伺碌尸箔癣竣延父牧跑煮网位疾槐糙窑线愿撵登辫高级数据结构高级数据结构92JYP5.3.2 插入操作插入操作 假假设设将将key为为4的的元元素素插插入入图图5.10所所示示的的双双堆堆。插插入入后后的的双双堆堆有有12个个元元素素，其其形形状状如如下下图图。j指指向向双双堆堆中中的新结点。的新结点。椰立址晒俱理梢旅序堰珠峨斡胶焰恼瑶草一弗烹喊塞泵席赘泼烯踪荷勇鳞高级数据结构高级数据结构93JYP 为为了了维维护护双双堆堆性性质质，首首先先比比较较4和和最最小小堆堆中中与与j对对应应结结点点i中中的的key值值，此此时时该该值值为为19。为为了了满满足足性性质质（4），将将key为为19的的元元素素移移到到结结点点j。由由于于19小小于于等等于于j的的双双亲亲结结点点的的key值值，移移动动后后最最大大堆堆性性质质仍仍然然保保持。持。 现现在在只只需需利利用用最最小小堆堆插插入入算算法法将将key为为4的的元元素素插插入入最最小小堆堆中中的的叶叶结结点点i并并调调整整即即可可得得到到下下一一页页所所示示的的双双堆。圆周加粗的结点的内容在插入过程中修改过。堆。圆周加粗的结点的内容在插入过程中修改过。格宗马挠呻蛋宁鹅狞绵畏资符识标侗拒珠酌狱伤汝管讫率憎予饮倚裂痘民高级数据结构高级数据结构94JYP生象鼻熏逞苯沙拐苦呜曳假巍油张新骤祷砚芝褥衙讨洁呼滴啮啄食矗穆封高级数据结构高级数据结构95JYP 如如果果将将key为为30的的元元素素插插入入图图5.10所所示示的的双双堆堆，插插入入后的双堆形状仍然如前面。后的双堆形状仍然如前面。 比比较较30和和与与j对对应应的的结结点点i中中的的key值值19，由由于于30大大于于19，只只需需利利用用最最大大堆堆插插入入算算法法将将key为为30的的元元素素插插入入最最大大堆堆中中的的叶叶结结点点j并并调调整整即即可可满满足足性性质质（4），并并得到下一页所示的双堆。得到下一页所示的双堆。酸津产题啼爪岿哟实伐豪靴午奢趋殴犬剩竿瓤渡坞狰颁减炯懂谅壹辰绩措高级数据结构高级数据结构96JYP蜂赂厚撞求宇扦达亡结品刺叹辐揪专见却妈滤园袒黑享豆魄蜕郭取批甩鸦高级数据结构高级数据结构97JYP 新结点新结点j是最小堆结点的情况与上面讨论的情况是最小堆结点的情况与上面讨论的情况对称。由此可得实现双堆插入操作的函数对称。由此可得实现双堆插入操作的函数Deap:Insert，其中又用到下列函数：，其中又用到下列函数：（1） Deap:DeapFull( )。（2） Deap:MaxHeap(int p)。判断。判断p是否最大堆结是否最大堆结点。对于点。对于p 1，当，当2 log2 p + 2 log2 p -1 p 2 log2 p 时，时，p是最大堆的结点。是最大堆的结点。（3） Deap:MinPartner(int p)。p是双堆的最后一是双堆的最后一个结点且为最大堆结点，计算与个结点且为最大堆结点，计算与p对应的最小堆结点，对应的最小堆结点，这可由这可由p 2 log2p -1 确定。确定。与嫩丽军卖闻彭藩琶潍拓锦锑峭瓜务饺牢疮抗淤振署漓猩谰讳呕邻隅减望高级数据结构高级数据结构98JYP（4） Deap:MaxPartner(int p)。p是双堆的最后一是双堆的最后一个结点且为最小堆结点，计算与个结点且为最小堆结点，计算与p对应的最大堆结点，对应的最大堆结点，这可由这可由(p + 2 log2p -1 ) / 2确定。确定。（5） 函数函数Deap:MinInsert和和Deap:MaxInsert分别分别将一个元素插入最小堆和最大堆的指定位置。与最将一个元素插入最小堆和最大堆的指定位置。与最小堆或最大堆的插入操作的区别仅仅在于此处最小小堆或最大堆的插入操作的区别仅仅在于此处最小堆的根是结点堆的根是结点2，最大堆的根是结点，最大堆的根是结点3。戴搏楞茁窒腐晌贵弘熟乘欺蝇毕狠政引玩霞揩沥诫哪甥劲醚郭余旧讣市纯高级数据结构高级数据结构99JYPtemplate void Deap:Insert (const Element&x ) / 将元素x插入双堆 int i; if (n = MaxSize ) DeapFull( ); return; n+; if (n = 1) d2 = x; return; / 插入空双堆 int p = n + 1; / p是双堆中新的最后位置 switch (MaxHeap(p) case TRUE: / p是最大堆结点 i = MinPartner(p); if (x.key di.key) dp = di; MaxInsert(i, x); else MinInsert(p, x); / switch结束 / Insert结束 分析：分析：插入操作所需时间与双堆的高度成线性关插入操作所需时间与双堆的高度成线性关系，其复杂性为系，其复杂性为O(log n)。词胆酿廖腋洁鸡胶藐材伙钮耀嗅列统庆黔讼程箍彤磐腥被噶室盎渊盖辩裁高级数据结构高级数据结构101JYP5.3.3 删除最小元素删除最小元素 删除最小元素的过程：删除最小元素的过程： 首先将从最小堆的根删除元素的问题转化为从最首先将从最小堆的根删除元素的问题转化为从最小堆的某一个叶结点删除元素的问题。这可通过沿小堆的某一个叶结点删除元素的问题。这可通过沿着从根到叶的路径检查，上调相关元素位置，保证着从根到叶的路径检查，上调相关元素位置，保证叶结点以上的层次满足最小堆性质实现。叶结点以上的层次满足最小堆性质实现。 这种转化使得空位由原来的最小堆的根变为叶结这种转化使得空位由原来的最小堆的根变为叶结点点i。这时再将原来双堆的最后一个元素。这时再将原来双堆的最后一个元素t插入叶结插入叶结点点i。将。将t插入双堆的叶结点插入双堆的叶结点i的过程与的过程与Deap:Insert基基本相同。但这时本相同。但这时Deap:MaxPartner(i)返回的返回的j应为：应为：j = i + 2log2i -1;if (j n + 1) j /= 2;沫逞麓掐特蝶磁钠寂莎计纽霞港秽料好汕考震檀扫捆芬旗摧歹搏趣捅柞踏高级数据结构高级数据结构102JYP 此外，如果结点此外，如果结点j中的元素的关键字小于中的元素的关键字小于t的关键的关键字，则需要将这两个元素交换，并根据需要调整从字，则需要将这两个元素交换，并根据需要调整从j到到t原来所在结点和原来所在结点和j的共同祖先的路径中的元素位的共同祖先的路径中的元素位置。置。 下一页给出了实现删除最小元素的函数下一页给出了实现删除最小元素的函数Deap:DeleteMin。盾随为啊领联嗡输粹毕齐棵家新崎溢馁蚤臼瓮烯妇蔓蒋竣布源旅箍炼晦拎高级数据结构高级数据结构103JYPtemplate Element* Deap:DeleteMin (Element&x ) / 删除并返回双堆的最小元素 if (!n) DeapEmpty( ); return; x = d2;/ 最小元素 int p = n+1; Element t = dp; / 最后一个结点中的元素 n-; for (int i = 2; i 至少有一个子女; i = j) 令j 为具有较小key值的子女; di = dj; 将 t 插入双堆的叶结点i; return &x;蔗前朋洁灾送千粤忿钟陶呀翟磨霸樊梢鹃颈刃誓纠宁媳括避琐峙鸭炳炯誓高级数据结构高级数据结构104JYP 假设从图假设从图5.10所示的双堆中删除最小元素。先将所示的双堆中删除最小元素。先将最后一个元素（最后一个元素（key为为20）存入临时变量）存入临时变量t。 接着，通过移动从结点接着，通过移动从结点2到叶结点路径上的元素到叶结点路径上的元素填充删除最小元素后在结点填充删除最小元素后在结点2形成的空位。每次都将形成的空位。每次都将当前结点的子女的较小元素上移，而被移动元素所当前结点的子女的较小元素上移，而被移动元素所在结点成为新的当前结点。于是，叶结点在结点成为新的当前结点。于是，叶结点10为空位。为空位。 结点结点10在最大堆的对应结点的在最大堆的对应结点的key值是值是40。由于。由于20 40，不必交换。继续将，不必交换。继续将key为为20的元素插入最小的元素插入最小堆的叶结点堆的叶结点10，可得下一页的双堆。，可得下一页的双堆。空薛坍住蓖依沸檄瘟声脑骆讫渊帝的獭怔跺潞常堑臂防孽耿输茵畅缅隔胰高级数据结构高级数据结构105JYP 分析：分析：删除最小元素操作所需时间与双堆的高度删除最小元素操作所需时间与双堆的高度成线性关系，其复杂性为成线性关系，其复杂性为O(log n)。枷炔祁证勇盐址塌县歉凯獭氮舀规泊侗釉阿梧猿到夷玉坑舟价背馅碧拄袭高级数据结构高级数据结构106JYP左偏树左偏树 (5.4) 本节考虑对优先队列另一种扩展本节考虑对优先队列另一种扩展合并操作，合并操作，即，将两个优先队列合并为一个。即，将两个优先队列合并为一个。 作为合并操作的一个应用，当一个优先队列的工作为合并操作的一个应用，当一个优先队列的工作服务器关闭时，需要将该优先队列与另一个正在作服务器关闭时，需要将该优先队列与另一个正在工作的服务器的优先队列合并。工作的服务器的优先队列合并。 设需要合并的两个优先队列的元素共有设需要合并的两个优先队列的元素共有n个。若个。若用左偏树，则优先队列的一般操作和合并操作都可用左偏树，则优先队列的一般操作和合并操作都可在在O(log n)时间内完成。时间内完成。 解汤广谁韭纂姥劣弓哩溢鄂追淋绒平巳钻埠机祟旱垮熏翔闸哮沿澎烬氦匿高级数据结构高级数据结构107JYP 左偏树左偏树可通过扩展二叉树定义。可通过扩展二叉树定义。扩展二叉树扩展二叉树是一是一棵二叉树，其中所有的空二叉子树都由方结点替代。棵二叉树，其中所有的空二叉子树都由方结点替代。扩展二叉树的方结点称为扩展二叉树的方结点称为外部结点外部结点。二叉树原来的。二叉树原来的（圆）结点称为（圆）结点称为内部结点内部结点。线洱刨曼淹昆鸣煤谰疡淘喷瞧己战塑荚铃起浅畸督烹醋绩汽高追等拉淮庇高级数据结构高级数据结构108JYP 下图为两棵二叉树，与之对应的扩展二叉树如下下图为两棵二叉树，与之对应的扩展二叉树如下一页所示。一页所示。祥枉拈讨梯畦径戈讳逐湾凛票钱撂冤攒蔫膊灿峻怪捶遇粉抑钩惜僵纠氛蹈高级数据结构高级数据结构109JYP屯焰烫泰噬苗买啪监疹瓤唁咽咙绣卷摇衍慨锋予皂踏翘痞毙冉汕涩踊辩壶高级数据结构高级数据结构110JYP 设设x是扩展二叉树的一个结点，是扩展二叉树的一个结点，LeftChild(x)和和RightChild(x)分别表示内部结点分别表示内部结点x的左子女和右子女。的左子女和右子女。 定义定义shortest(x)为从为从x到一个外部结点的最短路径到一个外部结点的最短路径的长度，则有：的长度，则有： 0 若若x是一个外部结点是一个外部结点shortest(x) = 1 + min shortest(LeftChild(x)， shortest(RightChild(x) 否则否则策油宾园么震溃半邀黎笋分救盎滚坍谬庭冬垒刁扒倦字椽璃窖沟驴篡攒宰高级数据结构高级数据结构111JYP 图图5.16的每个内部结点的每个内部结点x旁的数字是旁的数字是shortest(x)值。值。 定义：左偏树定义：左偏树是一棵二叉树，且满足下列性质：是一棵二叉树，且满足下列性质：若该树不空，那么对于其中的每一个内部结点若该树不空，那么对于其中的每一个内部结点x，有，有shortest(LeftChild(x)shortest(RightChild(x)。 图图5.15（a）的二叉树不是左偏树。图）的二叉树不是左偏树。图5.15（b）的二叉树是左偏树。的二叉树是左偏树。碾旧机射砰软央纷狼懂萝旋鸵秋半托稚幼林集落胖尤苦匆赶玛大茁绥眷嚏高级数据结构高级数据结构112JYP 引理引理5.1：设设x是具有是具有n个（内部）结点的左偏树的个（内部）结点的左偏树的根，则根，则（a） n2shortest(x) 1。（b） 最右边的从根到外部结点路径是最短的从根最右边的从根到外部结点路径是最短的从根到外部结点路径，其长度为到外部结点路径，其长度为shortest(x)。 证明：证明：（a）根据）根据shortest(x)定义，左偏树的前定义，左偏树的前shortest(x)层不存在外部结点层不存在外部结点鲍移盂雕场绥捶尘饿滔歉北舰钎诱限瓣抨泣闲苛刻绰乡幻翘炒堕侧丑豹仔高级数据结构高级数据结构113JYP因此该左偏树至少有因此该左偏树至少有 shortest(x) levels个内部结点。个内部结点。福涂私伪荡捶抑滁桂涡挚旗辱挑吁没掘龚忍猖热紧橱孕谦刹酵契馒跳球欢高级数据结构高级数据结构114JYP（b）可由左偏树的定义直接得出。）可由左偏树的定义直接得出。 假设左偏树的结点元素类型为假设左偏树的结点元素类型为Element，Element含有一个含有一个key数据成员。数据成员。 定义：定义：最小（最大）左偏树是一棵左偏树，其中最小（最大）左偏树是一棵左偏树，其中每一个内部结点元素的每一个内部结点元素的key值不大于（小于）该结点值不大于（小于）该结点子女（如果存在的话）的子女（如果存在的话）的key值。值。 即，最小（最大）左偏树是一棵左偏树，同时是即，最小（最大）左偏树是一棵左偏树，同时是一棵最小（最大）树。一棵最小（最大）树。惋隐肌鹃翔釉总题汛浑杭挣宦柔维犁但陡谗焚悟恐牵噪浮撑莆稚狱帖窟斑高级数据结构高级数据结构115JYP 下面是两棵最小左偏树：下面是两棵最小左偏树：经荔奶束扳迸悦己令妈保忿靛鲸付俯彦杆趣昏蒋倔轮乓噬闹腹衫昼剃粗剃高级数据结构高级数据结构116JYP 左偏树的类定义：左偏树的类定义：template class MinLeftistTree;template class LeftistNode friend class MinLeftistTree;private: Element data; LeftistNode *LeftChild, *RightChild; int shortest;template class MinLeftistTree: public MinPQ public: 铭疟恶是陪吏式缸奉离梯迂丑尿夹赎磷啃甭倦为毕溢宿女腔调拆产澈倦储高级数据结构高级数据结构117JYP MinLeftistTree(LeftistNode* init =0) : root(init) ; / 左偏树的三个操作 void Insert (const Element&); Element* Delete(Element&); / 删除最小元素 void MinCombine(MinLeftistTree*);private: LeftistNode*MinUnion(LeftistNode*, LeftistNode*); LeftistNode* root; 曹璃遭骑萝摆绕土佛及彰梢脑璃邯笼阿炼稼宛擎蜒犹惯告承馒翅昨坡何坡高级数据结构高级数据结构118JYP 由于对称性，下面只讨论最小左偏树。采用左偏由于对称性，下面只讨论最小左偏树。采用左偏树可使插入、删除最小元素以及合并操作在对数时树可使插入、删除最小元素以及合并操作在对数时间内完成。间内完成。 插入和删除最小元素操作都可以通过合并操作实插入和删除最小元素操作都可以通过合并操作实现：现：（1）将元素）将元素x插入一棵最小左偏树时，可先建立一插入一棵最小左偏树时，可先建立一棵包含单个元素棵包含单个元素x的最小左偏树，再合并这两棵最小的最小左偏树，再合并这两棵最小左偏树。左偏树。（2）从一棵非空最小左偏树中删除最小元素时，可）从一棵非空最小左偏树中删除最小元素时，可合并这棵最小左偏树的左、右子树，再删除其根结合并这棵最小左偏树的左、右子树，再删除其根结点。点。筏蓉盅必次撇努丧缄乙镑魔早古迸谦锻捡肄蹄涛例决刁谎蓖丧胶挠蚀惠陪高级数据结构高级数据结构119JYP 合并合并可以用递归来实现：可以用递归来实现： 2a 5b+= 2a 5(a)犹哀详忿伯延挠獭嚷匆将铆单骄淄捆这初鸳诚脚牢鸽牺艳区泞娟罪甄买首高级数据结构高级数据结构120JYP 必要时交换必要时交换a的左、右子树。的左、右子树。 2a 5b+= 2a通过结合通过结合c和和b 得到的左偏得到的左偏树树.(b)c讣息眶泰蒙池认菇钠蔗插丫券煤民莹烤贰脖渍前瞄族垢爬迭仟镣绿糠可溶高级数据结构高级数据结构121JYP 合并两棵分别以结点合并两棵分别以结点a和和b为根的最小左偏树：为根的最小左偏树： 比比较较结结点点a和和b的的key值值，若若a的的key值值不不大大于于b的的key值，则值，则a是合并所得树的根。是合并所得树的根。 a的的左左子子树树暂暂时时不不变变。递递归归调调用用算算法法，将将a的的右右子子树树与与以以b为为根根的的最最小小左左偏偏树树合合并并，所所得得最最小小左左偏偏树树成成为为a的新右子树。的新右子树。 若若该该新新右右子子树树的的根根结结点点的的shortest值值大大于于a的的左左子子树树的根结点的的根结点的shortest值，则交换值，则交换a的左、右子树。的左、右子树。 最后计算结点最后计算结点a本身的本身的shortest值。值。脾方环箍懒歹攻捡愿彤迢眉愉咆湘樊篷更迄战稠乒坝骨涤疆掏暂碰磷梯培高级数据结构高级数据结构122JYP a的的key值值大大于于b的的key值值的的情情况况也也类类似似处处理理，只只是是这时这时b是合并所得树的根。是合并所得树的根。 下下面面以以合合并并图图5.17的的两两棵棵最最小小左左偏偏树树为为例例，说说明明上上述述过过程程。为为简简化化描描述述，称称key值值是是k的的元元素素所所在在结结点为结点点为结点k。涕穷另丛悔符听粤焕每韵镍骄裕悼碧填问给泞匹树衅病肿芦坷识恨矛渊历高级数据结构高级数据结构123JYP 首首先先比比较较这这两两棵棵树树的的根根结结点点的的key值值2和和5。由由于于2 5，新最小左偏树的根结点应是结点，新最小左偏树的根结点应是结点2。耳九蚜稽既滨镜焕矛粮昆哩兆吝拿仁惑触佛庆郝鸦溃痪醛匙讣韩暮赂在蛮高级数据结构高级数据结构124JYP 再再将将根根为为结结点点50的的子子树树与与以以结结点点5为为根根的的最最小小左左偏偏树树合合并并。由由于于5 50，所所以以结结点点5是是新新最最小小左左偏偏树树的根。的根。匈任捶遁泡抓腐树棘踩海裹叁坯靠暂吁马离纺账闭嫉悦扔株皮孰据蝇谭旱高级数据结构高级数据结构125JYP 接接着着合合并并以以结结点点50为为根根的的最最小小左左偏偏树树和和以以结结点点8为为根根的的最最小小左左偏偏树树。由由于于8 shortest(结结点点9) = 1，需需要要交交换换结结点点5的的左左、右右子子树树，从从而而得得到到下下面面的的最最小小左偏树：左偏树：炯弓工夕嫡磋炔新翟磅弄麻蠕良漏桂跟藕聘牢晤彝屠碧泵佩掐压淹乓任趣高级数据结构高级数据结构127JYP 又又由由于于shortest(结结点点5) = 2 shortest(结结点点7) = 1，需需要要交交换换结结点点2的的左左、右右子子树树，最最终终得得到到下下一一页页所所示的最小左偏树。示的最小左偏树。 经过交换的指针用虚线表示。经过交换的指针用虚线表示。 脊妻稍萧涤典过昂他供判淮春俩腆踊革滴厦行妻牵耀别鹿演剐妙卓琶粹豆高级数据结构高级数据结构128JYP蜀门岩每垫孽怨健棺商狈便究纳阉矿美尽容镑窝眯渍凿耙狄测溉嘘毖哎免高级数据结构高级数据结构129JYP 实现最小左偏树合并操作的函数：实现最小左偏树合并操作的函数：template void MinLeftistTree:MinCombine (MinLeftistTree b) / 合并最小左偏树b和 / *this，并将b设置为空最小左偏树 if (!root) root = b.root; else if (b.root) root = MinUnion(root, b.root); b.root = 0;template LeftistNode* MinLeftistTree:MinUnion (LeftistNode*a, LeftistNode*b) / 合并以a和b为根的非空最小左偏树，并返回/ 所得最小左偏树的根。捷雷永抠其擞陀惕狸两简须代凤任愉彪读防燕狄掷搬嘶埠捶缺客雄馒嫡专高级数据结构高级数据结构130JYP if (adata.key bdata.key) / 令a指向根结点中key值 LeftistNode*t = a; / 较小的最小左偏树 a = b; b = t; / 构建最小二叉树 if (!aRightChild) aRightChild = b; else aRightChild = MinUnion(aRightChild, b); / 维护左偏树性质 if (!aLeftChild) / 左子树为空，交换左、右子树 aLeftChild = aRightChild; aRightChild = 0; 悬您灸迁甄蛾晕鲜忽卫哭仇泪耪吁咆膨模跺葬摔惑柏评癣识线贪愚裴眩伐高级数据结构高级数据结构131JYP else if (aLeftChildshortest aRightChild shortest) LeftistNode* t = aLeftChild; / 交换左、右子树 aLeftChild = aRightChild; aRightChild = t; / 设置shortest 数据成员 if (!aRightChild) ashortest = 1; else ashortest = aRightChildshortest + 1; return a;缸亥骤河专闪镜秧党婉咕序堵笛范堰迅噬叫晶维贯奥线袖妻焕絮夏盂如介高级数据结构高级数据结构132JYP 分析：分析：设两棵被合并的左偏树共有设两棵被合并的左偏树共有n个元素，由个元素，由于于MinUnion沿着两棵被合并的左偏树的最右路径下沿着两棵被合并的左偏树的最右路径下移，每棵左偏树的最右路径长度不超过移，每棵左偏树的最右路径长度不超过O(log n)，因，因此合并操作的时间复杂性为此合并操作的时间复杂性为O(log n)。糊墨破论艳传倡鸯仆送什拘灵墅孺隆纤沥裔慈锅休光羞农伯搀揣取赎脱蔼高级数据结构高级数据结构133JYP二项式堆二项式堆 (5.5) 二二项项式式堆堆支支持持与与左左偏偏树树相相同同的的功功能能（即即插插入入、删删除最小元素以及合并）。除最小元素以及合并）。 但左偏树的各个操作需要但左偏树的各个操作需要O(log n)时间。时间。 在在二二项项式式堆堆中中，插插入入与与合合并并操操作作可可用用O(1)时时间间完完成，而一次单独的删除最小元素可能需要成，而一次单独的删除最小元素可能需要O(n)时间。时间。 然然而而，如如果果将将删删除除最最小小元元素素操操作作的的代代价价分分摊摊到到插插入入操操作作上上，则则插插入入操操作作的的分分摊摊代代价价仍仍然然是是O(1)，合合并并操操作作的的分分摊摊代代价价与与其其实实际际代代价价相相同同，而而删删除除最最小小元素操作的分摊代价变为元素操作的分摊代价变为O(log n)。釜杰遂镇竞告惧烘筑烈示睁久琉翱隋珍镰静揍党坞事唆网戌澄刘等航开窑高级数据结构高级数据结构134JYP5.5.1 二项式堆定义二项式堆定义 定义：度为定义：度为k的二项式树的二项式树（记作（记作Bk）定义为：若）定义为：若k = 0，则该树只有一个结点；若，则该树只有一个结点；若k 0，则该树的根是，则该树的根是度为度为k的结点，其子树为的结点，其子树为B0，B1，Bk-1。 引理引理5.2：二项式树二项式树Bk具有具有2k个结点。个结点。 证明：证明：对对k应用归纳法。当应用归纳法。当k = 0，显然成立。假，显然成立。假设设k m时成立。则当时成立。则当k = m时，该树共有时，该树共有1 + 20 + 21 + ，+ 2m-1 = 2m 个结点。个结点。 最小二项式堆最小二项式堆最小二项式树的集合最小二项式树的集合 最大二项式堆最大二项式堆最大二项式树的集合最大二项式树的集合 由于对称性，下面只考虑最小二项式堆，并将其由于对称性，下面只考虑最小二项式堆，并将其简称为简称为B堆。堆。窍羞划娟扳就虐湖嗽川镍墒挥柞葬渐藉钒牛秦匹团贷君痘蕊族胚衙捐度铱高级数据结构高级数据结构135JYP 下图是一个由三棵最小二项式树构成的下图是一个由三棵最小二项式树构成的B堆：堆：娇挫知赁盅盘饭娇二宪惭沧酚急暑镰度标颜哀腰彝龚秘饱前煞猴涸壬瞎篆高级数据结构高级数据结构136JYP 二项式树的类定义：二项式树的类定义：template class BinomialHeap; / 向前声明template class BinomialNode friend class BinomialHeap;private: Element data; BinomialNode *child, *link; int degree;称婚刚泌帚烯韶将插囤负螟洞募肇恢租狂香就琵幅帘粪赶睛茨皂月取贝誓高级数据结构高级数据结构137JYPtemplate class BinomialHeap: public MinPQ public: BinomialHeap(BinomialNode*init = 0): min(init) ;/ 构造函数 void Insert (const Element&);/ 插入操作 Element* Delete(Element&);/ 删除最小/ 元素操作 void MinCombine(BinomialHeap*);/ 合并操作private: BinomialNode* min;蓝傣肝悸距卜苍谬梆菜阜纶兄丈陈亮柬牡埠骆盯耸监吐榆妆荡恫舷耻鹏湖高级数据结构高级数据结构138JYP 一一个个结结点点的的degree表表示示该该结结点点的的子子女女个个数数，child指指向向该该结结点点的的一一个个子子女女（如如果果存存在在的的话话），link用用于于构造由兄弟组成的单链环表。构造由兄弟组成的单链环表。 一一个个结结点点的的所所有有子子女女构构成成一一个个单单链链环环表表，而而该该结结点点的的child指向这些子女中的一个。指向这些子女中的一个。 构构成成B堆堆的的最最小小二二项项式式树树的的根根结结点点也也链链接接成成一一个个单单链链环环表表（注注意意，不不要要求求该该单单链链环环表表中中的的二二项项式式树树具具有有不不同同的的度度），整整个个B堆堆可可以以通通过过数数据据成成员员min访访问问，min指向指向key最小的根结点。最小的根结点。瑰怨惫早坷淮泞籍炎扑靖斧世林凤富吴纷挝桔谭徐整设氟销届绳撵肉辛朴高级数据结构高级数据结构139JYP 由此表示图由此表示图5.19的的B堆可得下图：堆可得下图：怠琉袖苛壶铜燎封酸镜备争泊阐榆心屎树碾胀扑饲蚕偏撒赚致皿残钨嗜论高级数据结构高级数据结构140JYP 其中，用双箭头将同一个单链环表的结点连接起来。其中，用双箭头将同一个单链环表的结点连接起来。 集集合合10，6，5，4，20，15，30，9，12，7，16和和8，3，1分分别别表表示示图图中中各各单单链链环环表表的的key值。值。 由由于于1是是三三个个根根结结点点中中的的最最小小key值值，min指指向向key为为1的根结点。的根结点。 空空B堆的堆的min值为空指针值为空指针0。 得掳秃孵王勺朴幼竖钧舌谰想摇傲携爪汇迸苛酮咖迢家沙浙蚕兹之岿辣优高级数据结构高级数据结构141JYP5.5.2 插入操作插入操作 将元素将元素x插入插入B堆可以如下实现：堆可以如下实现： 先先将将元元素素x存存入入一一个个新新结结点点，然然后后将将此此结结点点插插入入由由min指指向向的的单单链链环环表表。如如果果min = 0或或x.key小小于于min所指结点中的所指结点中的key值，则令值，则令min指向此新结点。指向此新结点。 这些插入步骤显然可用这些插入步骤显然可用O(1)时间完成。时间完成。诚窍罕藕啤褂焕闰吕款揩诚诧汪浊照浮壮碱核枢郸禾钝乓篓夕作廓廊擂寒高级数据结构高级数据结构142JYP5.5.3 合并操作合并操作 为为了了合合并并两两个个非非空空B堆堆，可可将将这这两两个个B堆堆的的顶顶层层单单链环表合并为一个。链环表合并为一个。 新新B堆堆的的指指针针是是原原来来两两个个B堆堆的的min指指针针之之一一，且且其其所指结点中的所指结点中的key值较小。这只需一次比较即可确定。值较小。这只需一次比较即可确定。 由由于于可可用用O(1)时时间间将将两两个个单单链链环环表表合合并并为为一一个个，合并操作只需合并操作只需O(1)时间。时间。赤己酒泡缠跺祝冠虱酵竹伟阿械鲤炳傀自掉涵钻膀庸茁异渭茧返援豪强勾高级数据结构高级数据结构143JYP5.5.4 删除最小元素删除最小元素 若若min = 0，则，则B堆为空，无法删除。堆为空，无法删除。 假设假设min 0，则，则min指向含最小元素的结点。指向含最小元素的结点。 从顶层环表中删除该结点。从顶层环表中删除该结点。 新新的的B堆堆由由剩剩余余的的最最小小二二项项式式树树和和被被删删除除结结点点的的子子树（也是最小二项式树）构成。树（也是最小二项式树）构成。园烬鞭麻业铆氧荤吧举冲速需省渗呸琼咒闸酱浸联互竣已及周窗缅痘资跌高级数据结构高级数据结构144JYP 例如，从图例如，从图5.19的的B堆中删除含最小元素堆中删除含最小元素灌灶斗茧一肛讹属船悦锦退燥图啄塔店富浚镁息恼珍股谐惯糖美仗跃蘑贤高级数据结构高级数据结构145JYP 得到：得到： 署牛照玄疮邯回奸枯惮饶塌穗沟谣阁蜒了穆尘叹察浚吁榔粤剑技蹲疆假郸高级数据结构高级数据结构146JYP 在在形形成成最最小小二二项项式式树树根根结结点点的的单单链链环环表表之之前前，反反复复结合度相同的一对最小二项式树。结合度相同的一对最小二项式树。 结结合合最最小小二二项项式式树树a和和b时时，若若a的的根根结结点点中中key值值较较大大，则则将将a作作为为b的的根根的的子子树树；否否则则将将b作作为为a的的根根的的子树。子树。 两两棵棵最最小小二二项项式式树树结结合合后后，所所生生成成的的最最小小二二项项式式树树的的度度比比原原来来增增加加1，顶顶层层最最小小二二项项式式树树的的总总个个数数减减少少1。 例例如如，可可以以结结合合以以结结点点8和和结结点点7为为根根的的一一对对最最小小二二项项式式树树或或以以结结点点3和和结结点点12为为根根的的一一对对最最小小二二项项式式树。树。漳龟恶孩祈兰剪沁粤咸刁蓬腑鉴谤转丁摇烯椭掉弦娶止班更嗅鸳讶牵评佰高级数据结构高级数据结构147JYP 若若结结合合第第一一对对，则则以以结结点点8为为根根的的最最小小二二项项式式树树成成为结点为结点7的一棵子树。于是得到下面的的一棵子树。于是得到下面的B堆：堆：芯纯敝宇榷脊矗覆顶粤蹋嘉踌堵你办盈探愚股掀局具猪钙倚肋噪败苟烙荐高级数据结构高级数据结构148JYP 其其中中有有三三棵棵度度为为2的的最最小小二二项项式式树树。若若再再结结合合以以结结点点7和和结结点点3为为根根的的一一对对最最小小二二项项式式树树，则则得得到到下下图图所示的所示的B堆：堆：秆菌槛谎邢凭叔慈崖惮研康滚还俐肮乘攫虎眉戳索促岛捻喀坎层疮糖嗓错高级数据结构高级数据结构149JYP 这这时时B堆堆中中的的最最小小二二项项式式树树的的度度都都不不一一样样，结结合合过过程结束。程结束。 接接着着，将将最最小小二二项项式式树树的的根根结结点点链链接接起起来来，形形成成单单链链环环表表，并并设设置置B堆堆指指针针min，使使其其指指向向含含最最小小key值的树根。值的树根。录复亢殿荫跋形摧息唾塞姻枯铜缉失贵马亏苑俗赣吨榆抱融恍赶澜绣拧蔫高级数据结构高级数据结构150JYP 由此可得删除最小元素操作所需的步骤：由此可得删除最小元素操作所需的步骤：template Element * BinomialHeap:DeleteMin (Element& x) / 删除B-堆的最小元素 第1步: 处理空B-堆 if (!min) DeleteError( ); return 0; 第2步: 从非空B-堆中删除 x = mindata; y = minchild; 将min所指向的结点从其环表中删除; 删除之后， min可指向新的环表中的任意一个结点; 如果无剩余 结点，则min = 0; 第3步: 结合最小二项式树 扫描由min和y指向的表，反复 结合具有相同度的最小二项式树对，直到剩余的最 小二项式树的度都不一样为止;氟壶奔候囱裕卫皖酮扯娄湘竖卡嘲肃彩降见孺戌瞄遣桐掐兹约画堆酣员矽高级数据结构高级数据结构151JYP第4步: 形成最小二项式树的根环表 链接剩余最小二项式 树（如果存在的话）的根结点，形成单链环表; 设 置min，使其指向含最小key值的根结点（如果存在 的话）; return &x; 第第1步步用用O(1)时间。时间。 第第2步步可通过将结点可通过将结点min的下一个结点的下一个结点next的内容的内容复制到结点复制到结点min，再删除结点，再删除结点next实现，这只用实现，这只用O(1)时间。时间。 第第3步步可用数组可用数组tree实现，实现，tree的下标范围是的下标范围是0到最到最小二项式树的最大可能的度小二项式树的最大可能的度MaxDegree。蟹挚仔年寐冷脾段附莫犯舞档搽桃演籽绽钙常么照又飘娟邑蔬沃麓烽缅阐高级数据结构高级数据结构152JYP 初初始始时时，数数组组tree的的所所有有单单元元都都设设置置为为0。设设s为为第第2步步生生成成的的表表min和和表表y中中最最小小二二项项式式树树的的总总个个数数。扫扫描描表表min和和表表y。对对于于表表min和和表表y中中的的每每一一个个最最小小二项式树二项式树p，执行下列代码：，执行下列代码： for (d = pdegree; treed; d+) JoinMinTree(p, treed); / 结合两棵最小二项式树 treed = 0; / 树treed 已被结合进p中 treed = p;/ 结合后，度比原来增加1 其其中中，JoinMinTrees使使输输入入参参数数表表示示的的最最小小二二项项式式树树中中根根结结点点具具有有较较大大key值值的的树树成成为为另另一一棵棵树树的的根根的的子树，所生成的新树通过第一个参数返回。子树，所生成的新树通过第一个参数返回。蔫廷岔喉赶牲嫉幼术流史捉夏摇缚喷谍爆言秤膜刊彪汗节醋化缓吻贯止求高级数据结构高级数据结构153JYP 最最终终，数数组组tree包包含含需需要要在在第第4步步中中链链接接起起来来的的最最小小二二项项式式树树的的根根结结点点指指针针。由由于于每每结结合合一一对对最最小小二二项项式式树树，最最小小二二项项式式树树的的总总数数减减少少1，总总的的结结合合次次数数最最 多多 是是 s 1。 因因 此此 ， 第第 3步步 的的 时时 间间 复复 杂杂 性性 是是O(MaxDegree + s)。 第第4步步可可通通过过扫扫描描tree0，treeMaxDegree并并链链接接找找到到的的最最小小二二项项式式树树来来完完成成，顺顺便便确确定定具具有有最最小小key值值的的根根结结点点。显显然然，第第4步步的的时时间间复复杂杂性性是是O(MaxDegree)。煮芽疯酮阳寇绎箕蹿粟耕曼髓缴寂枪列矾争持尧推芜砾捶屏驱数硫汕澜鲜高级数据结构高级数据结构154JYP5.5.5 分析分析 显然，显然，B堆的插入、合并和删除最小元素操作保堆的插入、合并和删除最小元素操作保持其性质，即持其性质，即B堆中的树都是最小二项式树。堆中的树都是最小二项式树。 引理引理5.3：设设a是一个有是一个有n个元素的个元素的B堆，则堆，则a中每中每一棵树的度一棵树的度log2n。因此，。因此，MaxDegree log2n ，删除最小元素操作的实际代价是删除最小元素操作的实际代价是O(log n + s)。 证明：证明：由于由于a中的每一棵树都是最多有中的每一棵树都是最多有n个结点的个结点的二项式树，由引理二项式树，由引理5.2，这些树的度不大于，这些树的度不大于 log2n 。 籍妨森辈奴筒弗涪角缉蟹送汛通贿抵菇驰莽件放型刮文邵并邹颧裸纳葵域高级数据结构高级数据结构155JYP 定理定理5.1：如果将由如果将由n个插入、合并和删除最小元个插入、合并和删除最小元素操作组成的操作序列应用于一组初始为空的素操作组成的操作序列应用于一组初始为空的B堆，堆，则通过代价分摊可使每个插入和合并操作的分摊代则通过代价分摊可使每个插入和合并操作的分摊代价为价为O(1)，每个删除最小元素操作的分摊代价为，每个删除最小元素操作的分摊代价为O(log n)。 证明：证明：对于每一个对于每一个B堆堆 如下定义如下定义#insert：当创建初始空：当创建初始空B堆或在堆或在B堆上堆上完成删除最小元素操作时，将其完成删除最小元素操作时，将其#insert设置为设置为0。每次在每次在B堆上完成插入操作时，其堆上完成插入操作时，其#insert值加值加1。两个两个B堆合并后产生的新堆合并后产生的新B堆的堆的#insert值为被合并值为被合并的两个的两个B堆的堆的#insert值之和。因此，一个值之和。因此，一个B堆的堆的#insert实际实际直睁仲呕淳由来孤谅拎拳窃耍堕朋鹊铭莽膨昆酬葬喜晒冒驻糯猴瞧给羚投高级数据结构高级数据结构156JYP上是自该上是自该B堆或其组成堆或其组成B堆（在涉及合并操作的情况堆（在涉及合并操作的情况下）最近一次删除最小元素操作以来完成的插入操下）最近一次删除最小元素操作以来完成的插入操作次数。作次数。 如下定义如下定义LastSize：当创建初始空：当创建初始空B堆时，将其堆时，将其LastSize设置为设置为0。当在一个。当在一个B堆上完成删除最小元堆上完成删除最小元素操作时，将其素操作时，将其LastSize设置为删除完成后设置为删除完成后B堆中包堆中包含的最小二项式树的数目。两个含的最小二项式树的数目。两个B堆合并后产生的堆合并后产生的新新B堆的堆的LastSize值为被合并的两个值为被合并的两个B堆的堆的LastSize值值之和。之和。 不难看出，一个不难看出，一个B堆的最小二项式树的数目堆的最小二项式树的数目= #insert + LastSize。锑仗贪兄张穷铬蜗旷慌诱思诉庐晌抢贬脂共凭角抄仁肉慑圃铝疆宗违肃账高级数据结构高级数据结构157JYP 考虑操作序列中的任何一个删除最小元素操作。考虑操作序列中的任何一个删除最小元素操作。假设该操作针对假设该操作针对B堆堆a。由于在。由于在n个操作的序列中最个操作的序列中最多有多有n个插入操作，所有个插入操作，所有B堆的全部元素最多为堆的全部元素最多为n个。个。 设设u = a.mindegree，则，则ulog2n。 根据引理根据引理5.3，该删除最小元素操作的实际代价是，该删除最小元素操作的实际代价是O(log n + s)。s这一项代表了扫描表这一项代表了扫描表min和表和表y并完成并完成最多最多s 1次最小二项式树结合所需的时间。由于结次最小二项式树结合所需的时间。由于结点点min的子树个数为的子树个数为u，而，而min所指最小二项式树被所指最小二项式树被删除，这时删除，这时s = #insert + LastSize + u 1。细嫌暂钩烬蓖抡斯遍镊榨意筋蒂佬冗幂矫狮晓寐肝简巳中镑发溺卡藩妮物高级数据结构高级数据结构158JYP 如果将如果将#insert个代价单位分摊到形成个代价单位分摊到形成#insert计计数的插入操作，并将数的插入操作，并将LastSize个代价单位分摊到形个代价单位分摊到形成成LastSize计数的删除最小元素操作（每一个删除计数的删除最小元素操作（每一个删除最小元素操作分摊的代价单位数目与该操作遗留的最小元素操作分摊的代价单位数目与该操作遗留的最小二项式树的数目相同），则只剩下最小二项式树的数目相同），则只剩下u 1个代价个代价单位。单位。 由于由于ulog2n且删除最小元素操作遗留的最小二项且删除最小元素操作遗留的最小二项式树的数目式树的数目log2n，删除最小元素操作的分摊代价，删除最小元素操作的分摊代价为为O(log2n)。灸钻妇曲孜磷哑刻靛肾勉锰簇渍余蔑敲带玉忿豫赃蛆札隋株膀睫右誊舰部高级数据结构高级数据结构159JYP 对于任何插入操作，我们在其实际代价基础上增对于任何插入操作，我们在其实际代价基础上增加了最多加了最多1个代价单位，因此其分摊代价为个代价单位，因此其分摊代价为O(1)。 合并操作未分摊任何额外代价，因此其实际代价合并操作未分摊任何额外代价，因此其实际代价和分摊代价相同，都是和分摊代价相同，都是O(1)。 根据上述定理和代价分摊的定义可知，任何由根据上述定理和代价分摊的定义可知，任何由i个个插入、插入、c个合并和个合并和dm个删除最小元素操作组成的序列个删除最小元素操作组成的序列的实际代价是的实际代价是O(i + c + dm log i)。摆资禾羌琵笆项颖塔辕啼唁巴甭嫡减渍庶帐痰掂梗阴姚梢掷傣冉匣领婪迭高级数据结构高级数据结构160JYP斐波纳契堆斐波纳契堆 (5.6)5.6.1 斐波纳契堆定义斐波纳契堆定义 斐波纳契堆斐波纳契堆是一种数据结构，该结构不仅支持二是一种数据结构，该结构不仅支持二项式堆的插入、删除最小（最大）元素与合并这三项式堆的插入、删除最小（最大）元素与合并这三个操作，而且支持下列新操作：个操作，而且支持下列新操作：（1） 减少减少key：将指定结点的：将指定结点的key减去一个正值。减去一个正值。（2） 删除：删除指定结点的元素。删除：删除指定结点的元素。 这两个新操作的第一个可用这两个新操作的第一个可用O(1)的分摊代价完成，的分摊代价完成，第二个操作可用第二个操作可用O(log n) 的分摊代价完成。其余操的分摊代价完成。其余操作的渐进时间与在二项式堆中的相同。作的渐进时间与在二项式堆中的相同。诗鲁恩狗会哎蚂噎三腾叁惜桌愤昨霄暮剧拎渝讳比又腰谰肥庞具狡疙椭姑高级数据结构高级数据结构161JYP 斐斐波波纳纳契契堆堆也也分分为为最最小小和和最最大大两两种种。最最小小斐斐波波纳纳契契堆堆是是最最小小树树的的集集合合，最最大大斐斐波波纳纳契契堆堆是是最最大大树树的的集集合合。由由于于对对称称性性，下下面面只只考考虑虑最最小小斐斐波波纳纳契契堆堆，并将其简称为并将其简称为F堆。堆。 B堆堆是是F堆堆的的特特殊殊情情况况，上上一一节节的的B堆堆实实例例也也是是F堆实例。堆实例。荧某连锁除剪章肚拇亨塘魁遭坤篓租锣烹避偶裙居肝望闺灰颊稍鸵绘诉垄高级数据结构高级数据结构162JYP F堆的表示：堆的表示： 在在B堆堆的的每每个个树树结结点点中中增增加加两两个个数数据据成成员员：parent和和ChildCut。parent用用于于指指向向该该结结点点的的双双亲亲（若若存存在的话）。在的话）。ChildCut用于控制最小树的修剪。用于控制最小树的修剪。 为为便便于于删删除除任任何何指指定定结结点点，用用双双链链环环表表代代替替B堆堆中中的的单单链链环环表表，即即将将原原B堆堆的的树树结结点点中中的的link换换为为LeftLink和和RightLink。 插插入入、删删除除最最小小元元素素与与合合并并这这三三个个基基本本操操作作的的实实现与在现与在B堆中的一样。堆中的一样。 下下面面重重点点考考虑虑两两个个新新操操作作：（1）从从F堆堆中中删删除除任任意结点意结点b；（；（2）将任意结点）将任意结点b的的key减去一个正值。减去一个正值。 自拦涯倔墅蔡纂稳炙羞贤丽秉惭诫躯狭跑蔡叼寥衣牟启误胃翼挂缎柜拣膨高级数据结构高级数据结构163JYP5.6.2 删除操作删除操作 从从F堆中删除任意结点堆中删除任意结点b可由如下步骤实现：可由如下步骤实现：（1） 若若min = b，则执行删除最小元素操作；否则，则执行删除最小元素操作；否则执行下列第（执行下列第（2）、（）、（3）和（）和（4）步。）步。（2） 将将b从其所在双链表中删除。从其所在双链表中删除。（3） 将将b的子女的双链表与由的子女的双链表与由min指向的根结点的指向的根结点的双链表合并，双链表合并，并将并将b b的子女结点的的子女结点的parentparent字段设置为字段设置为0 0，形成一个新的根结点双链表。与删除最小元素操形成一个新的根结点双链表。与删除最小元素操作不同的是，在此不结合度相同的树。作不同的是，在此不结合度相同的树。（4） 释放结点释放结点b。 惊宿画拘贱姑颧鲤辣瓮傲袋矗抡购抛育啄孽擒暮挣球元撑镰厂癣奏藕熟互高级数据结构高级数据结构164JYP 例如，从图例如，从图5.19的的F堆中删除含堆中删除含12的结点，的结点，擂密病窖乾骤来扛疵嘛哑庙谍离揪咒罪明亢暴宾劈穿顷技都绞涪多末日逗高级数据结构高级数据结构165JYP 则得到下面的则得到下面的F堆：堆： 当当min b时时，任任何何删删除除操操作作的的实实际际代代价价为为O(b的的度度)。当当min = b时时，删删除除操操作作的的时时间间就就是是删删除除最最小小元素操作的时间。元素操作的时间。土督损难锗渺邹逝嘲捡楷绸灌妈鸳殊割宣操髓吧音乞朽窒痹掌掩航并跨锐高级数据结构高级数据结构166JYP5.6.3 关键字减少操作关键字减少操作 减少结点减少结点b中的中的key可由如下步骤实现：可由如下步骤实现：（1） 减少减少b中的中的key值。值。（2） 若若b min且且b中的中的key值小于其双亲中的值小于其双亲中的key值，则将值，则将b从其所在双链表中删除并将其插入最小树从其所在双链表中删除并将其插入最小树根结点的双链表。根结点的双链表。（3） 若若b中的中的key值小于值小于min中的中的key值，则将值，则将min指向指向b。斗斡屯荫矫哮已摔扣篓多驹怂吴矽孟魏畜鸡拆澜贮屎遁资听敞次业液贪称高级数据结构高级数据结构167JYP 例如，将图例如，将图5.19的的F堆中的堆中的key 15减去减去4,蛹蹲填炭欺蜀糖忧猾碳剐类犊蔼戈蹈冈陈簇寨文捞拦翁际字码赌酉滥汹搓高级数据结构高级数据结构168JYP 得到的得到的F堆如下所示：堆如下所示： 减少减少key操作的代价是操作的代价是O(1)。瓣劝意轿糜样翰悸谊锨鲍戊壮嚏胚抗选诣狠泻对才契涧般蒂殖婿半愤自诸高级数据结构高级数据结构169JYP5.6.4 瀑布修剪瀑布修剪 由于删除任意结点和减少由于删除任意结点和减少key操作，操作，F堆中的最小堆中的最小树不一定是二项式树。因此，定理树不一定是二项式树。因此，定理5.1的分析不再有的分析不再有效。效。 为了保证每棵度为为了保证每棵度为k的最小树有的最小树有ck（c 1）个结）个结点，每个删除任意结点和减少点，每个删除任意结点和减少key操作之后还必须进操作之后还必须进行行瀑布修剪瀑布修剪。 为此，在每个结点增加为此，在每个结点增加ChildCut数据成员，其值数据成员，其值仅对不是最小树根的结点有意义。对于不是最小树仅对不是最小树根的结点有意义。对于不是最小树根的结点根的结点x，xChildCut为为TRUE当且仅当在最近当且仅当在最近一次一次x成为其双亲的子女后，成为其双亲的子女后，x的一个子女被删除。的一个子女被删除。们杀荚尖墩篷锄乎圃祥嫌先裤纶墩疆狠症蓉店祷留航基寡泻蚜柞鹊馅翅炮高级数据结构高级数据结构170JYP 而且，一旦删除任意结点或减少而且，一旦删除任意结点或减少key操作将不是操作将不是最小树根的结点最小树根的结点q从其双链表中删除，将引发瀑布修从其双链表中删除，将引发瀑布修剪过程。剪过程。 设设q的双亲为的双亲为p，瀑布修剪检查从，瀑布修剪检查从p到到q的的ChildCut值为值为FALSE的最近祖先的的最近祖先的路径路径所含结点。如果不存所含结点。如果不存在这样的祖先，则该路径为从在这样的祖先，则该路径为从p到包含到包含p的最小树的的最小树的根的路径。将该路径上所有根的路径。将该路径上所有ChildCut值为值为TRUE的的不是最小树根的结点从它们各自的双链表中删除，不是最小树根的结点从它们各自的双链表中删除，并加到并加到F堆的最小树的根结点的双链表中。若该路堆的最小树的根结点的双链表中。若该路径存在一个径存在一个ChildCut值为值为FALSE的结点，则将其的结点，则将其ChildCut设置为设置为TRUE。 钙撬椎稽馈妊傣定酪巨艇槛剩榔嫌趟雾署甜帧桂翌掏砚蹭吩简爷赤销恤夫高级数据结构高级数据结构171JYP图图5.26描述了将描述了将14减去减去4引起的瀑布修剪：引起的瀑布修剪：及谓咕咀泼栗赶凡蜂建疆掉昭韦并妨省恼桃骆节柞笼召觅潍弄寞瘪惧评旁高级数据结构高级数据结构172JYP5.6.5 分析分析 引理引理5.4：设设a是一个具有是一个具有n个元素的个元素的F堆，且堆，且a通通过在一组初始为空的过在一组初始为空的F堆上执行一系列插入、合并、堆上执行一系列插入、合并、删除最小元素、删除任意结点和减少删除最小元素、删除任意结点和减少key操作形成。操作形成。再设再设b是是a的任意最小树的任意结点，的任意最小树的任意结点，m是以是以结点结点b为根的子树的元素个数，为根的子树的元素个数， = ，则，则（a） b的度的度log m。（b） MaxDegree log n ，删除最小元素操作的，删除最小元素操作的实际代价是实际代价是O(log n + s)。 阀钩州逻黑玩恫聋瓢剖酣姓妹膨跺发乘文顽娠旦养鹃纂狼镀唯华哼藤促囊高级数据结构高级数据结构173JYP 证证明明：只只需需证证明明（a），（b）可可直直接接由由（a）推推出。出。 对对b的的度度应应用用归归纳纳法法。设设Ni是是以以度度为为i的的结结点点b为为根根的的子子树树的的最最少少元元素素个个数数。显显然然，N0 = 1，N1 = 2。因此，（因此，（a）对于）对于i = 0和和1成立。成立。 对对于于i 1，设设c1, , ci为为b的的i个个子子女女。假假设设cj在在cj+1（ji）之之前前成成为为b的的一一个个子子女女。因因此此，当当ck（ki）成为）成为b的一个子女时，的一个子女时，b的度至少为的度至少为k1。 唯唯一一能能使使一一个个结结点点成成为为另另一一个个的的子子女女的的F堆堆操操作作是是删删除除最最小小元元素素。因因此此，在在结结合合时时，ck的的度度一一定定等等于于b的度。的度。零抒困割配急贵枫锯妈脐哈哆川保陀蔷霓醇览防姚溪优谩谷舵洲逻盆汁舷高级数据结构高级数据结构174JYP 结结合合之之后后，作作为为删删除除和和减减少少key操操作作的的后后果果，ck的的度度可可能能减减少少。然然而而，结结合合之之后后ck的的度度最最多多可可减减少少1，因因为为删删除除ck的的第第二二个个子子女女将将引引起起位位于于ck的的瀑瀑布布修修剪剪。这这将将使使ck成成为为F堆堆的的最最小小树树的的根根，从从而而不不可可能能成成为为b的子女。的子女。 因因此此，ck的的度度dk至至少少是是max0，k 2。ck的的元元素素个数至少是个数至少是Ndk。 以以b为为根根的的子子树树包包括括1个个根根结结点点和和i个个子子女女（c1, , ci），c1的的度度至至少少为为0，c2, , ci的的度度分分别别至至少少为为0, , i 2，于是有，于是有族泅居权猾贫圆抚箱牵芯筐攫肥芜喀泼病柠谤蜡丹峰秃峦址喷肃跨埔蒋稼高级数据结构高级数据结构175JYP 而斐波纳契数而斐波纳契数Fn满足下列等式满足下列等式 由由此此可可得得，Ni = Fi+2，i0。根根据据斐斐波波纳纳契契数数理理论论，Fi+2 i，从而，从而Ni i。由于。由于Nim，所以，所以 ilog m。 托擞创祈剔奢读售戴坠谁碾逝辱老确岩秽泊斗辕朋触膜厨廊顶召罪义请来高级数据结构高级数据结构176JYP 定理定理5.2：如果将由如果将由n个插入、合并、删除最小元个插入、合并、删除最小元素、删除任意结点和减少素、删除任意结点和减少key操作组成的操作序列应操作组成的操作序列应用于一组初始为空的用于一组初始为空的F堆，则通过代价分摊可使每堆，则通过代价分摊可使每个插入、合并和减少个插入、合并和减少key操作的分摊代价为操作的分摊代价为O(1)，每，每个删除最小元素和删除任意结点操作的分摊代价为个删除最小元素和删除任意结点操作的分摊代价为O(log n)。整个操作序列的总时间复杂性是序列中各。整个操作序列的总时间复杂性是序列中各操作的分摊复杂性之和。操作的分摊复杂性之和。 证明：证明：证明与定理证明与定理5.1的类似。的类似。 #insert的定义不变。的定义不变。 对对LastSize需作如下扩充：在每次执行删除任意需作如下扩充：在每次执行删除任意结点和减少结点和减少key操作后，应根据操作后，应根据F堆中最小树棵数的堆中最小树棵数的净增量改变净增量改变LastSize的值。的值。才休饼契午疽禽售幼释巢酬肉吮饺涩卫焰柜转狙汕似袄父癣跌打迹绷黄坡高级数据结构高级数据结构177JYP 经过以上扩充，不难看出，在执行删除最小元素经过以上扩充，不难看出，在执行删除最小元素操作时操作时s = #insert + LastSize + u 1。 #insert个代价单位可分摊到形成个代价单位可分摊到形成#insert计数的计数的插入操作，每个插入操作分摊插入操作，每个插入操作分摊1个代价单位。个代价单位。 LastSize个代价单位可分摊到形成个代价单位可分摊到形成LastSize计数的计数的删除最小元素、删除任意结点和减少删除最小元素、删除任意结点和减少key操作。这使操作。这使得每个删除最小元素和删除任意结点操作分摊最多得每个删除最小元素和删除任意结点操作分摊最多log n的代价，减少的代价，减少key操作分摊操作分摊1个代价单位（瀑布个代价单位（瀑布修剪增加的最小树代价将在后面另外分摊）。因此，修剪增加的最小树代价将在后面另外分摊）。因此，删除最小元素操作的分摊代价是删除最小元素操作的分摊代价是O(log n)。炊瞎续浚钦粗胚炒嗣蜘芹钻耕链休腰旨凰如暮异林姓驾诊树镣挝果瘪谋给高级数据结构高级数据结构178JYP 只有删除任意结点和减少只有删除任意结点和减少key操作可能将结点的操作可能将结点的ChildCut设置为设置为TRUE，所以瀑布修剪的总次数受，所以瀑布修剪的总次数受到这些操作的总次数的限制。这些修剪的代价可分到这些操作的总次数的限制。这些修剪的代价可分摊到删除任意结点和减少摊到删除任意结点和减少key操作，每个操作分摊操作，每个操作分摊1个代价单位（包括瀑布修剪增加的最小树代价）。个代价单位（包括瀑布修剪增加的最小树代价）。 删除除了最小元素以外的其它元素的实际代价是删除除了最小元素以外的其它元素的实际代价是O(log n) ，且该操作从瀑布修剪分摊最多，且该操作从瀑布修剪分摊最多1个代价单个代价单位，从删除最小元素操作分摊最多位，从删除最小元素操作分摊最多log n个代价单位，个代价单位，所以其分摊代价是所以其分摊代价是O(log n)。彤雀据蛆砚搁飞稗申稽遵磐捻皋踢吴切燕咋杭逛叉湖检峙稿臃疹犬驼砾贡高级数据结构高级数据结构179JYP 减少减少key操作的实际代价是操作的实际代价是O(1) ，且该操作从瀑，且该操作从瀑布修剪分摊最多布修剪分摊最多1个代价单位，从删除最小元素操作个代价单位，从删除最小元素操作分摊最多分摊最多1个代价单位，所以其分摊代价是个代价单位，所以其分摊代价是O(1)。 插入操作的实际代价是插入操作的实际代价是O(1)，且该操作从删除最，且该操作从删除最小元素操作分摊最多小元素操作分摊最多1个代价单位，所以其分摊代价个代价单位，所以其分摊代价是是O(1)。 合并操作未分摊任何额外代价，因此其实际代价合并操作未分摊任何额外代价，因此其实际代价和分摊代价相同，都是和分摊代价相同，都是O(1)。 找丰抢特凝秃鸯敢娜丝陇狭脾察戒揖悯绣雄港授个尼阻源病滚挑惋底忽弘高级数据结构高级数据结构180JYP双连分量双连分量 (6.4.2) 双连分量在连通性方面比一般的连通分量具有更双连分量在连通性方面比一般的连通分量具有更高的要求，生成双连分量的操作也更复杂一些。高的要求，生成双连分量的操作也更复杂一些。 假设无向图假设无向图G是连通的，下面给出双连分量的正是连通的，下面给出双连分量的正式定义。式定义。 定义：定义：G的顶点的顶点v是一个是一个关节点关节点当且仅当从当且仅当从G中删中删除除v及其关联的边后，剩下的图至少有两个连通分量。及其关联的边后，剩下的图至少有两个连通分量。谴聊扰猫少抢辣某燃蚂盯绘霍均疮翔福皱吼猩贪豹询甄珍潭讫甲凿冲痹治高级数据结构高级数据结构181JYP 例例如如，在在下下面面的的连连通通图图G6中中，顶顶点点1，4和和7是是关关节节点。点。许茨戈澡楼楚妆袁仲啄林阜棠姓惟刊赣虎闭暖销涡涌清宣鲜普狈润曙置澳高级数据结构高级数据结构182JYP 定义：双连通图定义：双连通图是没有关节点的连通图。是没有关节点的连通图。 例如，图例如，图G5是双连通的：是双连通的：戍鲜吁撑诧认秀侥熄坞贱禽摩腊逾飞彰样暖仰优句钟栗偶掺鹊层疆诊闽媚高级数据结构高级数据结构183JYP 但图但图G6不是双连通的。不是双连通的。 在表示通信网络的图中，边表示通信链路，顶点在表示通信网络的图中，边表示通信链路，顶点表示通信站点，关节点显然是薄弱环节。表示通信站点，关节点显然是薄弱环节。 定义：定义：一个连通图一个连通图G的的双连分量双连分量是是G的最大双连的最大双连通子图。通子图。 时扑仪衍癸憎求他尚少杉绣辑桥浮咙誉碴做爆氯砷籍低慢俘乎吐绢典惺栏高级数据结构高级数据结构184JYP 图图G6包含四个双连分量，如下所示：包含四个双连分量，如下所示： 励必絮轴卵刀圣蜡艾斩惺烃轰涟芯肌芭灸丛收靶溺托私魁提牟聋梗绩蚂爷高级数据结构高级数据结构185JYP 不难发现，同一个图的两个双连分量最多有一个不难发现，同一个图的两个双连分量最多有一个共同顶点。由此可推出，一条边不可能出现在两个共同顶点。由此可推出，一条边不可能出现在两个或两个以上的双连分量中。因此，图或两个以上的双连分量中。因此，图G的双连分量的双连分量划分划分E(G)。 图图G的双连分量可利用的双连分量可利用G的任何深度优先生成树的任何深度优先生成树求得。求得。腑负衰碧撩附怔鸿碍晤熔庙峙订肛吵陕炮簧攘崭巩汁焙险怖堡抛汕技愈柜高级数据结构高级数据结构186JYP 图图G6的以顶点的以顶点0为根的深度优先生成树如下：为根的深度优先生成树如下：唬首儡秘娜勇苛翌倔歼溺囤悬煮纯漫澳淫滤耶惩掩冻芳葡闸芍揭姚问寿贸高级数据结构高级数据结构187JYP其中，非树边用虚线表示。顶点旁的数字称为该顶其中，非树边用虚线表示。顶点旁的数字称为该顶点的点的深度优先数深度优先数，简称为，简称为dfn。一个顶点的。一个顶点的dfn表示表示该顶点在深度优先搜索中被访问的顺序。该顶点在深度优先搜索中被访问的顺序。 例如，在前面的例如，在前面的G6生成树中，生成树中，dfn(0) = 1，dfn(1) = 2，以及，以及dfn(7) = 5。 注意，在深度优先生成树中，如果顶点注意，在深度优先生成树中，如果顶点u是是v的祖的祖先，则先，则dfn(u) dfn(v)。拄健瞒觉鞍钎栽纶梧价可缴绷城松峦踪珊也休丹巴缀蔷券漱获幸碰汁样缸高级数据结构高级数据结构188JYP 相相对对于于生生成成树树T，当当且且仅仅当当u是是v的的祖祖先先或或v是是u的的祖先时，非树边祖先时，非树边 (u, v) 才是一条才是一条回边回边。 例如，例如，(4, 1) 和和 (6, 7) 是回边。是回边。 不不是是回回边边的的非非树树边边称称为为横横边边。根根据据深深度度优优先先搜搜索索的的规规律律，相相对对于于任任意意一一个个图图的的任任何何深深度度优优先先生生成成树树，该图不可能有横边。该图不可能有横边。爽布圆呜裔昧硫妈烷杏挝樊蝎往光谐猩像菇廊卡蒂刻催麓咖掂写睁码马景高级数据结构高级数据结构189JYP 因因此此，深深度度优优先先生生成成树树的的根根是是关关节节点点的的充充分分必必要要条件是它至少有两个子女。条件是它至少有两个子女。 任任何何其其它它顶顶点点u是是关关节节点点的的充充分分必必要要条条件件是是u至至少少有有一一个个子子女女w，使使得得经经过过只只由由w，w的的后后代代以以及及一一条条回回边边构构成成的的路路径径不不可可能能到到达达u的的祖祖先先，因因为为删删除除顶顶点点u及其关联的边将使及其关联的边将使w及其后代与及其后代与u的祖先断开联系。的祖先断开联系。踊宁池氖九碘截温唉茫煎帛勺钥掩肿厅酞斋邱所嚏奴伊东掀祭耶鼓拘食如高级数据结构高级数据结构190JYP 假设顶点假设顶点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) 是一条回边是一条回边琳茁疫吏密矫苯纫套跺阎耗粗抑围肺晋键滴孟唆脏拔戴物烯绑则毁杭像登高级数据结构高级数据结构191JYP 于是，于是，u是关节点的充分必要条件是：是关节点的充分必要条件是：u或者是至或者是至少有两个子女的深度优先生成树的根，或者少有两个子女的深度优先生成树的根，或者u不是根不是根结点但有一个子女结点但有一个子女w，使得，使得low(w)dfn(u)。 下面是下面是G6的以顶点的以顶点0为根的深度优先生成树中各为根的深度优先生成树中各顶点的顶点的dfn和和low值：值： 顶点顶点01234567 dfn12734685 low12522555吗抱宗糠赤冰守拒满绪哗绿彼搜覆甜蜗汞楼宅琳傲腰搞观扬钡德恐币煮蚌高级数据结构高级数据结构192JYP 修修改改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;植矾镜非搬娩倡颧裹毁掘杏掘昔扒吨弄巨夕尽辽崖颓汉整积乔偏哭衔陆口高级数据结构高级数据结构193JYPvoid 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)不是回边坯服望徊苫恩彼轩窍咋幢赚藕涵候骗钡许购琵湿窘管铲疡欲纠寐榨峦税砧高级数据结构高级数据结构194JYP 注注意意，在在深深度度优优先先生生成成树树中中，若若v是是u的的双双亲亲，则则 (u, v) 一定不是回边。一定不是回边。 函函数数DfnLow(u, v)的的参参数数v就就是是为为区区分分这这种种情情况况而而设的。设的。 深深度度优优先先搜搜索索的的第第一一个个顶顶点点x无无双双亲亲，因因此此对对其其的调用形式为的调用形式为DfnLow(x, 1)。 函函数数DfnLow(u, v)用用到到的的另另一一个个函函数数min2返返回回其其两个参数的较小者。两个参数的较小者。停宇升炭蛀竣燕遇咐磺渍香屯硬笑幌敦谴畏捡嫡酌胀殴对好右檄罕朝匆啮高级数据结构高级数据结构195JYP 在在DfnLow的的基基础础上上进进一一步步处处理理，可可以以将将连连通通图图的边划分为双连分量。的边划分为双连分量。 注注意意，当当DfnLow(w, u)返返回回后后，loww已已计计算算好好。如果如果lowwdfnu，则可确定一个新的双连分量。，则可确定一个新的双连分量。 通通过过将将搜搜索索时时首首次次遇遇到到的的边边存存入入栈栈中中，可可以以求求得得一个双连分量的全部边。一个双连分量的全部边。缩讯翅尔吧呵桥胃遮被削绒惺肿弹哇博胎杉锻烤剿好膨鲤赶玫磋怀赁讨序高级数据结构高级数据结构196JYP 设设深深度度优优先先搜搜索索最最近近访访问问的的顶顶点点是是u，且且顶顶点点w与与u邻邻接接但但不不是是u的的直直接接双双亲亲，则则在在以以下下两两种种情情况况中中，(u, w)是首次遇到的边：是首次遇到的边： （1）w是未被访问的顶点是未被访问的顶点 （2）w是已被访问的顶点而且是是已被访问的顶点而且是u的祖先的祖先 由由于于未未被被访访问问的的顶顶点点的的dfn值值初初始始化化为为0，祖祖先先的的dfn值小于后代的，所以两种情况都可归结为值小于后代的，所以两种情况都可归结为dfnw dfnu，则则边边（w，u）一一定定已已经经作作为为回回边边（当当处处于于w点点时时）加加到到栈栈中中，如如下下所所示：示： uxw234效蜘篱礼韵衬傅木芜审潍痢评葱奶亭檄彻霜摔酋王涝讣状旨碰点牲脓术旧高级数据结构高级数据结构198JYP 函数函数Biconnected实现了上述过程：实现了上述过程：void Graph:Biconnected ( ) num = 1; dfn = new intn; low = new intn; for ( int i = 0; i 1。 dfnu = lowu = num+;违千锤赊仲惑坑渠搭暮蒙抿酌摄栖距偶疵织剁墙践裙吉吭诛卡绽奇冲萨蠢高级数据结构高级数据结构199JYP for (每一个与u邻接的顶点w) / 具体代码与图的表示有关 if (v != w & dfnw = dfnu) cout “新双连分量：” endl; do 从栈S删除一条边; 设此边为 (x, y); cout x , y endl; while ( (x, y)与(u, w)不相同); else if (w != v) lowu = min2 (lowu, dfnw); / 回边 / for结束 观僵赖柄疏顺丛瑰惨舰室凰倦械成缔庚獭苑税谩奋挎耿昧施醛殊紧哇李拥高级数据结构高级数据结构200JYP Biconnected的时间复杂性是的时间复杂性是O(n + e)。 注注意意，函函数数Biconnected假假设设输输入入的的连连通通图图至至少少有有两个顶点。两个顶点。 只只有有一一个个顶顶点点的的连连通通图图无无边边，但但按按定定义义，它它们们也也是双连通的。对此可作特殊处理。是双连通的。对此可作特殊处理。 嗓赚迅蓄寻泥睫槽齐玩韦铂饥剩魔梧蝶奥为贩硼菏渠踞蝎糙钞仑最许顷奸高级数据结构高级数据结构201JYP求解最小生成树的求解最小生成树的普瑞姆算法普瑞姆算法（6.5.2） 设设TV是是最最小小生生成成树树的的已已选选顶顶点点集集合合，T是是最最小小生生成成树树的的已已选选边边集集合合。普普瑞瑞姆姆算算法法首首先先任任选选图图G中中一一个顶点个顶点u，将，将u加入加入TV中。中。 然然后后将将一一条条代代价价最最小小的的边边 (u, v) 加加入入T中中，使使得得T (u, v)仍然是一棵树。仍然是一棵树。 重复上述步骤，直到重复上述步骤，直到T包含包含n 1条边为止。条边为止。 注注意意，(u, v) 关关联联的的两两个个顶顶点点必必有有一一个个在在TV中中，另一个不在另一个不在TV中。中。鲤拍摄姨任各羡趴数钙爱讫娜眶幻淑南卞曼鲍官摆找新轿地器魏赫叶键斗高级数据结构高级数据结构202JYP 普瑞姆算法的框架普瑞姆算法的框架: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 ;兴兰琼意蜘肚蝶昌龋旗辅焚丸卖挫匣黎衔狄窝人赏温到聂杉滥版红骑烬钱高级数据结构高级数据结构203JYP 用普瑞姆算法构造下图的最小生成树的过程：用普瑞姆算法构造下图的最小生成树的过程：或酌吨舀亥烽零涯劝康废谣庭缚著遁蚁孵剧爹痹泵饭颊植覆悄朱谤涩揭纯高级数据结构高级数据结构204JYP以赠涅膀笔奋滦彝娃娟烃蔽哪由础切零幂韭保妨弹防较潮库独润娜廉弊韦高级数据结构高级数据结构205JYP亦歌按的壤饶阳槐逼进弱僵弛跌挣字偏家底抿薄愁投壁蹈齿癸历将是渤零高级数据结构高级数据结构206JYP峻绣氰蓖晕淤行掘朴厢欣挎肆发鸳叙泼骆两澳港嚏枕殿坞岩黎寓颧狈疲硼高级数据结构高级数据结构207JYP 设设 是不属于是不属于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)。圣笔臂梁钠貌溶萧嘎涵够岭滤疵魂斜丑馋吴袭菊阿讳俐划钡稳扰雀自魔租高级数据结构高级数据结构208JYP 设设w是是 中与中与v邻接的顶点。顶点邻接的顶点。顶点v加入加入TV之之后，如果后，如果cost(v, w) cost(nearw,w) ，则将，则将nearw改为改为v。 由此可以有效地实现普瑞姆算法。由此可以有效地实现普瑞姆算法。 如果用邻接矩阵如果用邻接矩阵costij表示图表示图G，则算法的时，则算法的时间复杂性是间复杂性是O(n2)，因为算法总共选，因为算法总共选n 1个顶点，每个顶点，每选一个顶点选一个顶点v及处理及处理v对对nearw（w 且且w与与v邻邻接）的影响最多只需接）的影响最多只需O(n)时间。时间。墙存企囱片相蝗溺铂抄拓擂横谎痰苫坪例冗疗毖奢渗闯偷排醉座铀买琴狭高级数据结构高级数据结构209JYP 如如果果用用邻邻接接表表表表示示图图G并并利利用用斐斐波波纳纳契契堆堆，则则可可使使算算法法的的性性能能更更好好。对对于于v ，定定义义distv = cost(nearv,v)，可可理理解解为为顶顶点点v到到已已构构造造的的部部分分最最小生成树的最近距离。小生成树的最近距离。 每每次次往往TV中中加加入入一一个个顶顶点点，算算法法都都需需要要确确定定顶顶点点v，使使得得v ，且且distv = 。这这对应于对应于 上的删除最小元素操作。上的删除最小元素操作。 由由于于v加加入入TV， 中中与与v邻邻接接的的顶顶点点的的dist值值可可能减少。这对应于能减少。这对应于 上的关键字减少操作。上的关键字减少操作。孟础仔蹬蒜炊臻傲签舷朔间喝朝钢猩徒懂歇复钞碳舞搏连幌屑矢放妥窿帆高级数据结构高级数据结构210JYP 关关键键字字减减少少操操作作的的总总次次数数最最多多是是图图中中边边的的条条数数。删除最小元素操作的总次数是删除最小元素操作的总次数是n 1。 初初始始时时， 含含n 1个个顶顶点点。如如果果以以dist为为关关键键字字，将将 组组织织为为斐斐波波纳纳契契堆堆，则则需需要要n 1次次插插入入操操作作初始化斐波纳契堆。初始化斐波纳契堆。 接接着着需需要要执执行行n 1次次删删除除最最小小元元素素操操作作和和最最多多e次次关关键键字字减减少少操操作作。所所有有这这些些操操作作的的代代价价是是各各操操作作的分摊代价之和，即的分摊代价之和，即 O(n log n + e)。 因因此此，算算法法的的时时间间复复杂杂性性变变为为O(n log n + e)。当当e远小于远小于n2时，这显然是一种改进。时，这显然是一种改进。舆幂闰耐幼涝泞中君台唤壬甚稚聚唯仲卡呵弥琼榷耀滩蓝甘华炎抱颁冤春高级数据结构高级数据结构211JYP斐波纳契堆在斐波纳契堆在最短路径算法中的应用最短路径算法中的应用 先回忆一下经典的最短路径算法：先回忆一下经典的最短路径算法：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 & disti LARGEINT) pathi = v; else pathi = 1;5 6 sv = TRUE; distv = 0;7 for (i = 0; i n-2; i+) / 确定从v开始的n 1条路径8 int u = choose(n); / 选择u，使得对于所有sx = / FALSE，distu = 最小的distx9 su = TRUE;辛区润果卯锰唐埔烽爱览像雾背块市汤酪碾圃追之赡虞奈女雏椅奇峨靴其高级数据结构高级数据结构212JYP10 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 命兔驻酌柑动枯古掌琐寡羚馒株乳跳硕兽裳侍茂遮袖傣年沂竭名拧鹰泊紊高级数据结构高级数据结构213JYP 分析：分析：第第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)。 味炉子紊投困琼甄学猴院牵豌窜融阑啃易胡争鄙太谷句伯浮狰奈缮篮连协高级数据结构高级数据结构214JYP 应用斐波纳契堆应用斐波纳契堆和邻接表，可使算法的时间复杂和邻接表，可使算法的时间复杂性减少为性减少为O(n log n + e)。 每次迭代，都需要确定顶点每次迭代，都需要确定顶点u，使得，使得u ，且，且distu = 。这对应于。这对应于 上的删除最小上的删除最小元素操作。元素操作。 由于由于u加入加入S， 中与中与u邻接的顶点的邻接的顶点的dist值可能值可能减少。这对应于减少。这对应于 上的关键字减少操作。上的关键字减少操作。循拴置捏道形仆暇狡铺科教茁疹呸闽戎猾突吴衫亿搐园瑟榨帕蜕洗粗拎轿高级数据结构高级数据结构215JYP 初初始始时时， 含含n 1个个顶顶点点。如如果果以以dist为为关关键键字字，将将 组织为斐波纳契堆，则需要组织为斐波纳契堆，则需要n 1次插入操作。次插入操作。 接接着着需需要要执执行行n 2次次删删除除最最小小元元素素操操作作和和最最多多e次关键字减少操作。次关键字减少操作。 所所有有这这些些操操作作的的代代价价是是各各操操作作的的分分摊摊代代价价之之和和，即即 O(n log n + e)。 因此，算法的时间复杂性是因此，算法的时间复杂性是O(n log n + e)。 当当e远小于远小于n2时，这种实现显然更好。时，这种实现显然更好。 考察题考察题：P223 23（每个同学单独完成，并提（每个同学单独完成，并提交报告，作为本课程主要成绩因素）交报告，作为本课程主要成绩因素） 氧隐粪匹审啸佩晋麻妒淌竞佯加烦蝴酌蔚而贮鹏吝裴缨耶崔啮闻刨独兢胰高级数据结构高级数据结构216JYP基于链表和映射表排序结果的顺序化基于链表和映射表排序结果的顺序化（7.8） 对对于于基基于于链链表表的的排排序序结结果果，有有时时需需要要按按次次序序就就地地重新排列，使它们在物理上也是顺序的。重新排列，使它们在物理上也是顺序的。 设设记记录录表表R0, , Rn-1经经排排序序后后的的结结果果是是一一个个按按关关键键字字非非递递减减次次序序链链接接的的链链表表，且且first是是链链表表的的首首记记录指针。录指针。 将将记记录录R0和和Rfirst交交换换。如如果果first 0，则则表表中中应应有有一一个个记记录录Rx，其其link字字段段值值为为0。如如果果能能够够修修改改Rx的的link字字段段，使使其其指指向向原原位位于于R0的的记记录录的的新新位位置置first，则则剩剩余余记记录录R1, , Rn-1也也是是按按关关键键字字非非递递减减次次序序链链接的。接的。锐帛汁嫌谐灶扳彤址胜弛篓饶酥诬认薄编社存局医谤筐遥楷绢健魁抛碌伟高级数据结构高级数据结构217JYP 但但在在单单链链表表中中，我我们们无无法法快快速速确确定定结结点点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。乔息搔拇跌搜委赤邦替刮荡圣晦敢划嗅藤德胳谋浊淀狗择芹膜袁贺劫向鬃高级数据结构高级数据结构218JYP 同同时时，注注意意到到作作为为剩剩余余记记录录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;/ 经过虚拟结点捎台镣泡撒恭勉柴膝吐辙乳呜秸百稗访腺嘲先鉴百旭戎畔绣窜漱扎捡迭散高级数据结构高级数据结构219JYP 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; 幼迎蕴诬嚎薄盛嘱骤毖屑耪穗水淫郝积痰窒骚桶藐沁锦啄优宅肛笨镰污暇高级数据结构高级数据结构220JYP 例例7.9 对对 (26, 5, 77, 1, 61, 11, 59, 15, 48, 19) 进进行行链表排序后，所得链表如下所示：链表排序后，所得链表如下所示：册踢绘胀贷宪戌郑码端濒辣维份惭华堪亡诌歉虑狐阶霞厩她驴喊河颖萍蕾高级数据结构高级数据结构221JYP list的的for循循环环每每次次迭迭代代后后记记录录表表的的状状态态如如下下，变变化化用用粗粗体体字字表表示示，虚虚拟拟结结点点的的link字字段段用用带带下下划划线线的的字体表示：字体表示：梳馆唉畴扶踪仁殉紧晦丫骚又扇紊税总嫁江唤紧现杰棚算燕伴温脖嗡擂拌高级数据结构高级数据结构222JYP割生挡掖叁贱脓凸办艇取抖赠劝款余遥叫字诵眼并马妖料鳞怔兜是背氢央高级数据结构高级数据结构223JYP摧承投喝吹庚寨溪篡挑抗亡椰沿葡援虾屿炭捍耿你捅盒生雏佐礼员少苦役高级数据结构高级数据结构224JYP绩愤狐娟狙拭危丰依仲历恶窑哉宿姓扼擂字惯羌人氦大柞违坦嘎岳械差炽高级数据结构高级数据结构225JYP太阁扔烁郴爆姐穷眨奇澡阳师娃校氰铬伟讯核盒稚供按忘护郝轩嚎钢膝璃高级数据结构高级数据结构226JYP 对对list的的分分析析：设设有有n个个记记录录，for循循环环迭迭代代n1次次。每每次次最最多多交交换换2个个记记录录，需需要要3次次记记录录移移动动。如如果果每每个个记记录录的的长长度度为为m，则则每每次次交交换换的的代代价价是是3m。所所以以，最坏情况下记录移动的总代价是最坏情况下记录移动的总代价是O(mn)。 在在while循循环环中中，任任何何结结点点最最多多被被检检查查一一次次，所所以以while循环的总时间是循环的总时间是O(n)。 显然，显然，list所需的辅助空间是所需的辅助空间是O(m)。撕允秩奏汐闷衅首庇灶驼酿踌有搬蚀掺望吨箍自寒移刁售墓帝江围蒋盼拴高级数据结构高级数据结构227JYP 链链表表排排序序不不适适用用于于希希尔尔排排序序、快快速速排排序序和和堆堆排排序序，因为记录表的顺序表示是这些方法的基础。因为记录表的顺序表示是这些方法的基础。 对对于于这这些些方方法法可可以以采采用用映映射射表表t，表表的的每每一一个个单单元元对对应应一一个个记记录录。映映射射表表单单元元起起着着对对记记录录间间接接寻寻址址的作用。的作用。 排排序序开开始始时时，ti = i，0in1。如如果果要要求求交交换换Ri和和Rj，则则只只需需交交换换表表单单元元ti和和tj。排排序序结结束束时时，关关键键字字最最小小的的记记录录是是Rt0，最最大大的的记记录录是是Rtn-1，所所要要求求的的记记录录排排列列是是Rt0, Rt1, , Rtn-1，如如下下一一页页所所示。示。潞仅殊牢蛔询幻邹盛雅镀彩期藩俯舷颖素捕更弗终伪亚侈醚杉咋铬饯慕捍高级数据结构高级数据结构228JYP狭韩伺墒向东姥逝侮爸然沿观堪硬脉翔稳藻豌挨涕搭舍国哄会妊泥应资期高级数据结构高级数据结构229JYP 有时为了避免间接寻址，还需要根据映射表有时为了避免间接寻址，还需要根据映射表t确确定的置换在物理上重新排列记录。定的置换在物理上重新排列记录。 整个置换由不相交的环路组成。含记录整个置换由不相交的环路组成。含记录i的环路由的环路由i, ti, t2i, , tki构成，且构成，且tki = i。 例如，上一页的置换由两个环路组成，第一个包例如，上一页的置换由两个环路组成，第一个包含记录含记录R0和和R4，第二个包含记录，第二个包含记录R1，R3和和R2。 函数函数table首先沿着包含首先沿着包含R0的环路将记录移到其正的环路将记录移到其正确位置。接着，如果包含确位置。接着，如果包含R1的环路未被移动过，则的环路未被移动过，则沿着该环路将记录移到其正确位置。由此继续移动沿着该环路将记录移到其正确位置。由此继续移动包含包含R2, R3, , Rn-2的环路，最终得到物理上就序的环路，最终得到物理上就序的记录表。的记录表。 拦竭畏氓步普僻虑奏征枣醛陡远燕淘毛掘命正碌数丹稚柑不泡诉啥眯脊纺高级数据结构高级数据结构230JYPtemplate void table(Element *list, const int n, int *t) / 重新排列list0, , listn-1，使其对应序列listt0, , / listtn-1, n1 for (int i = 0; i n 1; i+) if (ti != i) / 存在一个开始于i的非平凡环路 Element p = listi; int j = i; do int k = tj; listj = listk; tj = j; j = k; while ( tj != i ); listj = p; / p中的记录应该移到位置j tj = j; 恰乘腾浴销骡曹脂晃蹦侨憋棱腹萌食凹凯中特僻闹贰取好革鬼媳指薄哭穆高级数据结构高级数据结构231JYP例例7.10 一个根据映射表一个根据映射表t对记录顺序化的例子：对记录顺序化的例子：还书诡鹅紊岩运是车撰割执牡躲落铬女圾筋嗡非察追阂擒园是低惶海侍渐高级数据结构高级数据结构232JYP 对对table的分析：的分析：设每个记录占用设每个记录占用m个存储单元，个存储单元，则所需辅助空间为则所需辅助空间为O(m)个存储单元。个存储单元。 for循环执行了循环执行了n1次。如果对于某些次。如果对于某些i的取值，的取值，ti i，则存在一个包含，则存在一个包含k 1个不同记录个不同记录Ri, Rti, , Rtk-1i的环路。重新排列这些记录需要的环路。重新排列这些记录需要k+1次移次移动。动。 设设kj是在是在for循环中循环中i = j时以时以Rj开头的非平凡环路开头的非平凡环路的记录个数。对于平凡环路，则令的记录个数。对于平凡环路，则令kj = 0。记录移动。记录移动的总次数是的总次数是给族朵澈略皂委父周搭啸弓绊沈奇襄玻铅何倔戚太每坍耿玻拘共损温炒蹄高级数据结构高级数据结构233JYP 当当 = n且存在且存在 n/2 个非平凡环路时，记录个非平凡环路时，记录移移动的总次数达到最大值动的总次数达到最大值 3n/2 。 移动一个记录的代价是移动一个记录的代价是O(m)，总的计算时间是，总的计算时间是O(m n)。尾湾漂姿欢话江舍澄仍髓菊掀可威狭政骄驱篇必铜龚以辅嘿钳薄胁毡卧图高级数据结构高级数据结构234JYP7.9 外排序外排序7.9.1 概述概述 需要排序的记录表大到计算机内存不能容纳时，需要排序的记录表大到计算机内存不能容纳时，内排序已不足以解决问题。内排序已不足以解决问题。 假设需要排序的记录表存放在磁盘上。由于计算假设需要排序的记录表存放在磁盘上。由于计算机访问内存的速度比访问磁盘的速度快得多，影响机访问内存的速度比访问磁盘的速度快得多，影响外排序外排序性能的主要是性能的主要是访问磁盘访问磁盘的次数。的次数。 磁盘的读、写以磁盘的读、写以IO块块为单位。一个为单位。一个IO块通常可块通常可包含多个记录。包含多个记录。柳咐侠传匝抹岸解祁篙捅坞至闷逼轿阉私已误之帅生渍腋腮姜坪飞臼雁逞高级数据结构高级数据结构235JYP 影响磁盘读写时间的有以下三个因素：影响磁盘读写时间的有以下三个因素：寻找寻找时间：将读写头定位于正确的柱面所用时间。时间：将读写头定位于正确的柱面所用时间。等待等待时间：本磁道中所需块旋转到读写头下所用时间：本磁道中所需块旋转到读写头下所用时间。时间。传输传输时间：将块中数据读入内存或写到磁盘所用时间：将块中数据读入内存或写到磁盘所用时间。时间。 其中，就数据传输而言，寻找和等待都是辅助性其中，就数据传输而言，寻找和等待都是辅助性的，但其时间却较长。为了提高传输效率，的，但其时间却较长。为了提高传输效率，IO块块的容量一般都较大，通常可包含数千字节。的容量一般都较大，通常可包含数千字节。筏怪牛眩擦守冕丁觉抨吓垫尤瓷犊惫舶淤倘鳖镭育咙蜗宦躇都晚酉爽云渝高级数据结构高级数据结构236JYP 外排序的最基本方法是归并，包括两个阶段：外排序的最基本方法是归并，包括两个阶段：（1）根根据据内内存存容容量量将将输输入入记记录录表表分分为为若若干干段段，并并利利用用某某种种内内排排序序方方法法逐逐个个对对这这些些段段排排序序。这这些些已已排排序的段又称为序的段又称为归并段归并段（runs）。）。（2）归归并并第第一一阶阶段段生生成成的的归归并并段段，直直到到最最终终只只剩剩一一个归并段。个归并段。 由由于于归归并并算算法法只只要要求求同同一一时时刻刻两两个个归归并并段段的的前前端端记记录录在在内内存存，因因此此经经过过归归并并，可可以以生生成成比比内内存存大大的的归并段。归并段。记目姓圾毅境寞槛邵峨躬抽困痰亡寓摊刷率隋帛蔡赵煎疯眉酣么兼枣穴氟高级数据结构高级数据结构237JYP 例例7.11 设记录表有设记录表有4500个记录，可用于排序的计个记录，可用于排序的计算机内存容量是算机内存容量是750个记录，个记录，IO块长度是块长度是250个记录。个记录。按上述方法，排序步骤如下：按上述方法，排序步骤如下：下昧眉麓丈桐败洋吸饼淋污释蹄批育脂手阐后缓绢狡丰樱最背寞邱恕氰数高级数据结构高级数据结构238JYP喷歹趾徐童摊圾汗唬行症砧妊壮悍谎让毁换哇覆刁寐愚侨讨织坝忻皇毁盼高级数据结构高级数据结构239JYP分析用符号：分析用符号：tseek = 最长寻找时间最长寻找时间tlatency = 最长等待时间最长等待时间trw = 读写一个读写一个IO块（块（250个记录）所需时间个记录）所需时间tIO = tseek + tlatency + trwtIS = 内排序内排序750个记录所需时间个记录所需时间ntm = 将将n个记录从输入缓冲区归并到输出缓冲区所个记录从输入缓冲区归并到输出缓冲区所 需时间需时间也碰枢住徊魂咬焊煽瑞匿扑界霄缀节兽熬悬遵龄洪曳淑长宣纵之醛砌缨阿高级数据结构高级数据结构240JYP例例7.11中排序中排序4500个记录的操作时间：个记录的操作时间：亦荡铲赁戒离岭谦长喧旅甥笋蹄扩懊坦猿此睡钳珊话填乃疡害盼卑某瑰狗高级数据结构高级数据结构241JYP 由于由于tIO tIS，tIO tm，影响计算时间的主要，影响计算时间的主要因素是输入输出操作的次数，而后者又主要依赖于因素是输入输出操作的次数，而后者又主要依赖于对数据扫描的遍数。对数据扫描的遍数。 例例7.11中，生成初始归并段需要中，生成初始归并段需要1遍数据扫描，遍数据扫描，归并需要归并需要 遍数据扫描。遍数据扫描。 一遍扫描需要输入输出一遍扫描需要输入输出2 18个个IO块，总的输入块，总的输入输输出时间是出时间是( + 1) 2 18tIO = 132tIO。 归并时间是归并时间是 4500tm = 12000tm。摔巢优佰具揪吐艘扼符喊崔倘儿障择云品承宅麓馁潭吾谬甭偶仔丈锰功笋高级数据结构高级数据结构242JYP 显然，显然，k路归并路归并（k 2）可以减少数据扫描遍数。）可以减少数据扫描遍数。例如，如果在上例中采用例如，如果在上例中采用6-路归并，则只需对数据路归并，则只需对数据扫描一遍即可完成排序。扫描一遍即可完成排序。 此外，初始归并段应尽可能长，从而减少初始归此外，初始归并段应尽可能长，从而减少初始归并段个数。并段个数。 在内存容量给定的情况下，可以利用动态流动的在内存容量给定的情况下，可以利用动态流动的思想，生成平均长度几乎是通常方法所得的两倍的思想，生成平均长度几乎是通常方法所得的两倍的归并段。归并段。 但这些归并段长短不一，对它们归并的次序也会但这些归并段长短不一，对它们归并的次序也会影响计算时间。影响计算时间。 下面将分别讨论这些问题。下面将分别讨论这些问题。拖览纤赁乍磨市治侍满略桔坤嫁蓖优妮汛星裕拍捞哮胰摸祥清砍峨真惦韧高级数据结构高级数据结构243JYP7.9.2 k k路归并路归并 按按2-路路归归并并，给给定定m个个归归并并段段，相相应应的的归归并并树树有有 log2m +1层，需要对数据扫描层，需要对数据扫描 log2m 遍。遍。 采采用用k路路归归并并可可减减少少数数据据扫扫描描遍遍数数。如如下下图图对对16个归并段进行个归并段进行4-路归并只需扫描数据路归并只需扫描数据2遍：遍：帆泞舒使剖括雕盐遏钉谁想恨雹冒渔矽贿狂捂加腐冀步质歉茸膝兼巍剔纹高级数据结构高级数据结构244JYP 一一般般地地，采采用用k路路归归并并需需要要对对数数据据扫扫描描 logkm 遍遍。因因此此，当当k 2时时，采采用用k路路归归并并可可有有效效减减少少输输入入输输出时间。出时间。 但但k路路归归并并要要求求从从k个个归归并并段段的的前前端端记记录录中中选选择择关键字最小的输出。关键字最小的输出。 可可以以采采用用具具有有k个个叶叶结结点点的的败败者者树树来来选选择择关关键键字字最最小小的的记记录录。从从败败者者树树中中每每选选一一个个最最小小记记录录并并重重新新调调整整需需要要O(log2k)时时间间，所所以以对对n个个记记录录归归并并一一遍遍需需要的时间是要的时间是O(n log2k)。 归归并并logkm遍遍的的CPU处处理理时时间间是是O(n log2k logkm) = O(n log2m)，即与，即与k无关。无关。培匠票辰凳摊暂铭清菠擒幢斗睫崇边雾溶最完竞挡臆掂红傈清婿漂崩讶改高级数据结构高级数据结构245JYP 还应该看到，当还应该看到，当k超过一定范围时，输入输出时超过一定范围时，输入输出时间并不随着间并不随着k的增大而减少。因为：的增大而减少。因为： k路归并所需的缓冲区个数随着路归并所需的缓冲区个数随着k的增大而增加；的增大而增加； 在内存容量给定情况下，缓冲区容量随着在内存容量给定情况下，缓冲区容量随着k的增的增大而减小；大而减小； 这又导致这又导致IO块的有效容量减小，从而使一遍数块的有效容量减小，从而使一遍数据扫描需要更多的据扫描需要更多的IO块操作。块操作。 因此，当因此，当k超过一定值时，输入输出时间反而会超过一定值时，输入输出时间反而会随着随着k的增大而增加。的增大而增加。k值的最佳选择与磁盘参数值的最佳选择与磁盘参数和可用于缓冲区的内存容量有关。和可用于缓冲区的内存容量有关。捆开别皱坠司镍家脆考渐菠扳差哑争茬雾梗汕厌准毕儡研赴摈甭桌忱袭迂高级数据结构高级数据结构246JYP7.9.3 生成初始归并段生成初始归并段 用用传传统统的的内内排排序序方方法法生生成成初初始始归归并并段段，需需要要将将内内存存容容纳纳的的所所有有记记录录都都排排序序好好后后再再全全部部输输出出到到磁磁盘盘。从从在在排排序序过过程程中中没没有有内内外外存存数数据据交交换换的的意意义义上上看看，这这属属于于静静态态方方法法，由由此此生生成成的的归归并并段段最最多多与与内内存存容容纳的记录数同样大。纳的记录数同样大。 如如果果采采用用动动态态流流动动的的方方法法，即即在在生生成成归归并并段段的的过过程程中中不不断断将将记记录录写写到到磁磁盘盘，同同时时从从磁磁盘盘读读入入新新的的记记录到内存，则可能生成比内存容量大的归并段。录到内存，则可能生成比内存容量大的归并段。芥鸿缎花饼罗茶孜簧捉冯原糖洋战柔吓准馆美府丹屡坏咀甭蹲烙熏辨是跺高级数据结构高级数据结构247JYP 设内存可容纳设内存可容纳k个记录，用个记录，用r0, r1, , rk1表表示，记录的输入和输出通过示，记录的输入和输出通过IO缓冲实现。缓冲实现。 输入输入k个记录后，这些记录都属于当前归并段。个记录后，这些记录都属于当前归并段。 从属于当前归并段的内存记录中选关键字最小的从属于当前归并段的内存记录中选关键字最小的记录记录rq（0q k）输出到当前归并段。）输出到当前归并段。 从输入表读入下一个记录到从输入表读入下一个记录到rq，如果此记录的，如果此记录的关键字不小于当前归并段的最后一个记录的关键字，关键字不小于当前归并段的最后一个记录的关键字，则该记录也属于当前归并段，否则属于下一个将生则该记录也属于当前归并段，否则属于下一个将生成的归并段。成的归并段。捐亦相惠洲长鼠世蹿牧汉糯兹毛孺薯啄算嫩菱计啃妹愈零圈屿漏罐死钒钡高级数据结构高级数据结构248JYP 将内存记录所属的归并段号作为第一子关键字，将内存记录所属的归并段号作为第一子关键字，记录原来的关键字作为第二子关键字，下一个要输记录原来的关键字作为第二子关键字，下一个要输出的记录是出的记录是k个记录中关键字最小的。个记录中关键字最小的。 败者树败者树是组织这些记录的有效结构：是组织这些记录的有效结构： 每个非叶结点每个非叶结点i有一个字段有一个字段li（1ik），表示在），表示在结点结点i比赛的败者。比赛的败者。 rni表示表示ri所属的归并段号（所属的归并段号（0ik）。）。 l0和和q都存放整个比赛的胜者记录下标。都存放整个比赛的胜者记录下标。 rc存放当前归并段号。存放当前归并段号。 rq存放存放rq所属的归并段号。所属的归并段号。缀补符行俄彬樱挖埔术蹿员兆抿摘卯颈懦价挝蝇莹钨赋渊相铆疵倔稼鸣屁高级数据结构高级数据结构249JYP rmax存放将生成的实际归并段总数。存放将生成的实际归并段总数。 LastKey存放当前最后一个输出记录的关键字值。存放当前最后一个输出记录的关键字值。 当输入记录表已读空时，我们可以构造归并段号当输入记录表已读空时，我们可以构造归并段号为为rmax + 1的虚拟记录，以将败者树中的实际记录的虚拟记录，以将败者树中的实际记录“顶顶”出。出。减你挠基尾剥皖览净震碱傻帛惺划做澎务承伺巷越但稍慢勾揍挝杭闪舔邵高级数据结构高级数据结构250JYP 函数函数runs实现了上述采用败者树动态流动生成初实现了上述采用败者树动态流动生成初始归并段的方法：始归并段的方法：1 template 2 void runs(const int k) 3 Element *r = new Elementk;4 int *rn = new intk; int *l = new intk;5 for ( int i = 0; i rmax ) break; / 遇到虚拟记录，说明实际 / 记录已输出完，跳出循环15 else rc = rq;16 17 WriteRecord(rq); LastKey = rq.key;18 / 输入新记录19 if (输入结束) rnq = rmax + 1; / 生成虚拟记录，以把实 / 际记录“顶”出败者树20 else 21 ReadRecord (rq);22 if ( rq.key LastKey) rnq = rmax = rq + 1; / 新记录 / 属于下一个归并段盈惠过混熄且涤堕蹄浅哦彬柒堡雁旨科畔昨说竣伸纬阂陋卜央诉慈秤止吱高级数据结构高级数据结构252JYP23 else rnq = rc; / 新记录仍然属于当前归并段24 25 rq = rnq;26 / 重新调整败者树27 for (int t = (k + q)/2; t; t /= 2) / t初始化为rq的父结点28 if (rnlt rq) | (rnlt = rq & rlt.key rq.key) / t是胜者29 int temp = q; q = lt; lt = temp;30 rq = rnq;31 32 / while循环结束33 delete r; delete rn; delete l;34椿电班响蹦醒嵌绰料擎抒临舔恐旬涵敝颂惭年脊柑妆臭煎刺硕燎延碑淮拄高级数据结构高级数据结构253JYP 例例7.12 设输入表为设输入表为 (99, 48, 19, 65, 3, 74, 33, 17, 21, 20, 98, 53, 22)，k = 4，则，则runs生成初始归并段的生成初始归并段的过程如后面所示：过程如后面所示：掂垄戚祸朱榔命妊衔邯标骂倒捎履毛豢浇台睫链皿肖则砸卷镇依馆蛹扮霖高级数据结构高级数据结构254JYP季窗删锈囤暑恢蔼借鳃班度隆肠弗舍熙葡甄冠踢士福鞭砷展滴栖滇塑圭锚高级数据结构高级数据结构255JYP作才耙顿拧孤榜甘秩辽茨呕进靖操奎对蕉洲嫂攘铜旱然赂隧姬渍灵波辐砒高级数据结构高级数据结构256JYP晒吠宁陆狭谚是鲍姬响灾诗歧铣钦脏想宁悲咸夏秉苟闸旺汐垫唉颧早负痰高级数据结构高级数据结构257JYP蜡烛预帛豢坝裴揖虚萝享纽嗡葵梗貉薯浓骇淬盂许屯镊纲丈效邻肾乘瑟怨高级数据结构高级数据结构258JYP蚕义惦叉舒伟奏浇酝诬筹速绝侣综碴苏味褥锨懦唯蓟洒请疟郊斗泄敬解巍高级数据结构高级数据结构259JYP它律知爽肆初槽哗加尾呆燎垦亮林仇凌懒胁治辞摸腹侗趾屿灾与纽笔死爽高级数据结构高级数据结构260JYP悍陆根涵萍充浪府礁勘撕镇于需堆虚兔厅向郑卒管冒卡音成中窿假磊囱枝高级数据结构高级数据结构261JYP 分析：分析：当输入记录表已排好序，只生成一个归并当输入记录表已排好序，只生成一个归并段。平均而言，段。平均而言，runs生成的归并段长度是传统方法生成的归并段长度是传统方法的两倍。由于每输出一个记录，重新调整败者树的的两倍。由于每输出一个记录，重新调整败者树的时间是时间是O(log k)，所以对于，所以对于n个记录的输入表，生成个记录的输入表，生成所有归并段的时间是所有归并段的时间是O(n log k)。实验作业：实验作业：P26129镁驻投酵涣辐奔夸规庸滥械斟食亮晕媳当妨桔袍第叫闸搞磕茹色描础漂冰高级数据结构高级数据结构262JYP7.9.4 归并段的最佳归并和哈夫曼树归并段的最佳归并和哈夫曼树 由由runs生生成成的的归归并并段段长长短短不不一一定定相相同同。这这时时前前面面所所述述的的完完整整扫扫描描所所有有归归并并段段的的策策略略所所导导致致的的计计算算时时间不是最少的。间不是最少的。菱刁洞朋亢屉勾由陷租忠舀扭嗜估财浅盾晶摇沸桌纂壹亦各都嘱薛将奴搔高级数据结构高级数据结构263JYP 例例如如，假假设设有有四四个个归归并并段段，长长度度分分别别为为3，4，8和和21。可用下列两种方式给进行。可用下列两种方式给进行2-路归并：路归并：缚弗惫蹭宵铺叛斥赌胖喘菇父暇嚏娄吟颠深黑刃党托究州瞻僻炸出嘘络驻高级数据结构高级数据结构264JYP 一一个个记记录录参参与与的的归归并并次次数数由由其其所所在在的的外外部部结结点点到到根根的距离确定。的距离确定。 由由于于归归并并时时间间与与参参与与的的记记录录个个数数成成线线性性关关系系，总总的的归归并并时时间间应应等等于于所所有有归归并并段段的的长长度度与与其其相相应应的的外外部部结点到根的距离的乘积之和。结点到根的距离的乘积之和。 此和又称为此和又称为加权外部路径长度加权外部路径长度。 前面两棵树的加权外部路径长度分别是前面两棵树的加权外部路径长度分别是 3 3 + 4 3 + 8 2 + 21 1 = 58 和和 3 2 + 4 2 + 8 2 + 21 2 = 72。南擒可擦爹遮祝其犹鲸薪渺抓棋疤刁莫朔藻忠曝避蠢肠姜印况复半士伊竭高级数据结构高级数据结构265JYP 如果采用具有最短加权外部路径长度的如果采用具有最短加权外部路径长度的k叉归并叉归并树，则对树，则对n个长度为个长度为qi（1in）的归并段进行）的归并段进行k路归路归并的代价最小。并的代价最小。 这里仅考虑这里仅考虑k = 2的情况。的情况。 最短加权外部路径长度二叉树的另一个应用是获最短加权外部路径长度二叉树的另一个应用是获得最佳得最佳信息编码信息编码。 设需要建立信息设需要建立信息M1, M2, , Mn 的一组最佳编的一组最佳编码。每个编码为二进制位串。码。每个编码为二进制位串。 在接收端，通过解码树对编码进行解码。在接收端，通过解码树对编码进行解码。楔臭娇携念牡厚塑中旷骗泌油宫驰识姑绚捍挞煎谜馈寨储玖炙赤峭膀翅臭高级数据结构高级数据结构266JYP 解码树是一棵二叉树，解码树是一棵二叉树，其外部结点表示信息。信其外部结点表示信息。信息编码字中的二进制位决息编码字中的二进制位决定了到达正确外部结点需定了到达正确外部结点需经过的各层分枝。经过的各层分枝。 例如，将例如，将0解释为左分枝，解释为左分枝，1为右分枝，右图的解码树为右分枝，右图的解码树就对应编码就对应编码000，001，01和和1，分别表示信息，分别表示信息M1, M2, M3和和M4。逗遵陛跨下秋慎阁脓唉嚎宏化麻葛咱寿垃挨邓邵瀑腋边含剑盛娠俺润汾霹高级数据结构高级数据结构267JYP 解码的代价与编码位数成正比，而该位数就等于解码的代价与编码位数成正比，而该位数就等于相应的外部结点到根结点的距离。相应的外部结点到根结点的距离。 设设qi是传输信息是传输信息Mi的相对频率，的相对频率，di是是Mi对应的外对应的外部结点到根结点的距离，则期望解码时间是部结点到根结点的距离，则期望解码时间是 显然，通过选择具有最短加权外部路径长度的解显然，通过选择具有最短加权外部路径长度的解码树对应的编码，可使期望解码时间最短。码树对应的编码，可使期望解码时间最短。咙罚末蚁照淋芜栅搓末孽周自搭栏孩弛遏病侗猴唱渠怖鹤吻此劣罢铲证斥高级数据结构高级数据结构268JYP 哈哈夫夫曼曼给给出出了了建建立立具具有有最最短短加加权权外外部部路路径径长长度度的的二二叉树的有效方法，因此这种树又称为叉树的有效方法，因此这种树又称为哈夫曼树哈夫曼树。 设二叉树的类定义为：设二叉树的类定义为：class BinaryTreeNode friend class BinaryTree;private: BinaryTreeNode *LeftChild; int weight; BinaryTreeNode *RightChild;既漂氓砖煽燕旭饼年起灭攒盾倚值付文习流训冗详辱摊魔敛露杆镊最吠登高级数据结构高级数据结构269JYPclass BinaryTree public: BinaryTree(BinaryTree bt1, BinaryTree bt2) root = new BinaryTreeNode; rootLeftChild = bt1.root; rootRightChild = bt2.root; rootweight = bt1.rootweight + bt2.rootweight; private: BinaryTreeNode *root;促允搀咆绽鬼箔扒糟绑希我独恃拯杯哪盛液驰硼弓着磕灾痔潞嫂雅诲福甥高级数据结构高级数据结构270JYP 函数函数huffman利用一个由扩展二叉树构成的表利用一个由扩展二叉树构成的表list。void huffman(List list) int n = list.Size( ); / 表list中的二叉树棵数 for (int i = 0; i n 1; i+) / 循环n-1次，以结合n个结点 BinaryTree first = list.DeleteMinWeight( ); BinaryTree second = list.DeleteMinWeight( ); BinaryTree *bt = new BinaryTree(first, second); list.Insert(bt); 其中用到函数其中用到函数List:DeleteMinWeight( )，List:Size( )和和List:Insert( )。猾会漫戚饶绝馅喷栈让白矢椭短琢老富阳淬增熬血糟级以哮阑帚沥挣雪使高级数据结构高级数据结构271JYP list.DeleteMinWeight( )返返回回list中中权权重重最最小小的的树树并并将将其其从从list中中删删除除，list.Size( )返返回回list中中元元素素个个数数，list.Insert(bt)将新二叉树将新二叉树bt加入表加入表list中。中。竹拖无煞夸俱椭饯葫仁峭橱江哩巍橱韶郸钻鲁栽赔愿罪条婶枚饰戊盾刚履高级数据结构高级数据结构272JYP 例例7.13 设设权权重重q1= 2，q2= 3，q3= 4，q4= 7，q5= 8和和q6= 13，则所生成的树序列如下：，则所生成的树序列如下：墒伯梁采虑磨掌皑墩掘静寥暂急暑桌嘲参奉辽训困疼泼楔棉焚笔拜闺尊屋高级数据结构高级数据结构273JYP腊骤揭涌殆碍蚊碳躇咀嚼吠帝迷寝满灵捎孰被矾欧酋受争踏某缉滋射甭吞高级数据结构高级数据结构274JYP 最终所得哈夫曼树的加权外部路径长度是最终所得哈夫曼树的加权外部路径长度是 2 4 + 3 4 + 4 3 + 7 2 + 8 2 + 13 2 = 88 相比之下，最好的完全二叉树的外部路径长度是相比之下，最好的完全二叉树的外部路径长度是90。 分析：分析：主循环执行主循环执行n1次。将表次。将表list维护为一个最维护为一个最小堆，每次调用小堆，每次调用DeleteMinWeight和和Insert只需要只需要O(log n)时间，总计算时间是时间，总计算时间是O(n log n)。莽恕捅杉冤砍轩臃震绒涨粮抡瓢督诡括托高早既等蝎互桥未通抹墒疟商促高级数据结构高级数据结构275JYP 根据哈夫曼树，很容易获得一组信息的最佳编码。根据哈夫曼树，很容易获得一组信息的最佳编码。 另另外外，利利用用构构建建哈哈夫夫曼曼树树的的思思想想，反反复复删删除除和和归归并并当当前前长长度度最最短短的的两两个个归归并并段段，将将结结果果加加到到归归并并段段表表中中，直直到到表表中中只只剩剩下下一一个个归归并并段段，即即可可实实现现归归并并段的最佳归并。段的最佳归并。抑五放被镇接虎谅盒脐牛沉凄议靛答灰贫秸掖疚候忘羡装袁永拆蒙堆墓兜高级数据结构高级数据结构276JYP二叉查找树的结合与分裂二叉查找树的结合与分裂 （8.2.3）首先回顾二叉查找树的首先回顾二叉查找树的定义：定义： 二叉查找树是一棵二叉树。如果不空，该树应满二叉查找树是一棵二叉树。如果不空，该树应满足以下性质：足以下性质：（1） 每个元素有一个关键字，且任何两个不同的每个元素有一个关键字，且任何两个不同的元素的关键字不相等（即关键字唯一）；元素的关键字不相等（即关键字唯一）；（2） 左子树（如果存在的话）中的关键字小于根左子树（如果存在的话）中的关键字小于根结点中的关键字；结点中的关键字；（3） 右子树（如果存在的话）中的关键字大于根右子树（如果存在的话）中的关键字大于根结点中的关键字；结点中的关键字；（4） 左、右子树也是二叉查找树。左、右子树也是二叉查找树。拖硅碌便陕昆味蓉痈销玄蛀落析苛双渐捶停蛾党糜寓掣凶晒贸跨藕肩卢技高级数据结构高级数据结构277JYP二叉树的例子二叉树的例子:其中，（其中，（a）不是二叉查找树，（）不是二叉查找树，（b）和（）和（c）是。）是。 示啼疵疡楚熊那笔尚愁躺森誓掏糖迹硬于幻堤烷锻胯弓跪代毕嵌素插誓滇高级数据结构高级数据结构278JYP 除了查找、插入和删除操作以外，有的应用还需除了查找、插入和删除操作以外，有的应用还需要对二叉查找树进行下列操作：要对二叉查找树进行下列操作：（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设置为空。设置为空。岁慰派岛聚锄函汪抵柜寄酌容浙记新晌羡磅庆甜侨累忠冶签祷拷厦挑氖助高级数据结构高级数据结构279JYP（3） A.Split(i, B, x, C)： 分裂为三部分：分裂为三部分：B包含包含A中所有关键字小于中所有关键字小于i的元的元素；如果素；如果A含关键字为含关键字为i的元素，则将该元素复制到的元素，则将该元素复制到x，并返回，并返回x的指针，否则返回的指针，否则返回0；C包含包含A中所有关键中所有关键字大于字大于i的元素。最后将的元素。最后将A设置为空。设置为空。绣奸精臃兹堤现坐是循唁噶聪演枫缓逸冗汲舵涣粹调亩垮俯丘椽狞蜀环埠高级数据结构高级数据结构280JYP 3-路结合的实现：路结合的实现： 获获得得一一个个新新结结点点，使使其其成成为为C的的root，并并将将其其data字字 段段 设设 置置 为为 x， LeftChild字字 段段 设设 置置 为为 A.root，RightChild字段设置为字段设置为B.root。 最后将最后将A.root和和B.root设置为设置为0。 计计算算时时间间是是O(1)，新新树树C的的高高度度是是 maxheight(A), height(B)+1。凋钱志送躬盐纫覆字核么耍男独啪楼伙坪侥骇叉蚁拜谬挝俞字嚣氛伤独征高级数据结构高级数据结构281JYP 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。申烽佐屹匠跨讲绑氨钎灵测壁抽挽凿哮训落绊苫疥福渠喷笼熙皿滔吐舀矣高级数据结构高级数据结构282JYP 分裂操作的实现：分裂操作的实现： 在在根根结结点点（即即i = A.rootdata.key）的的分分裂裂很很容容易易。这这时时，B是是A的的左左子子树树，x是是根根结结点点元元素素，C是是A的右子树，如图的右子树，如图8.4（a）所示。）所示。 如如果果i小小于于根根结结点点的的关关键键字字，根根结结点点及及其其右右子子树树应应属于属于C，如图，如图8.4（b）所示。）所示。 如如果果i大大于于根根结结点点的的关关键键字字，根根结结点点及及其其左左子子树树应应属于属于B，如图，如图8.4（c）所示。）所示。秽智届兰堕蜡粱茫癌埂诀拄聋柠宗衷漓囊脖慑集旋美寥般借疡睹抬帜惶灰高级数据结构高级数据结构283JYP序蛙宵逐裂顺袋廓农旨汲讨森旋腹榴壹焚软桑拖伎伏虹黍掖谩港栋宗饵刹高级数据结构高级数据结构284JYP 一一般般地地，可可以以在在A中中向向下下查查找找关关键键字字为为i的的元元素素的的过程中构造二叉查找树过程中构造二叉查找树B和和C。设。设t指向当前结点。指向当前结点。 若若i tdata.key，则结点，则结点t及其左子树应加入及其左子树应加入B中。中。 若若i = tdata.key，则则应应将将t的的左左、右右子子树树分分别别加加入入B、C中，并将中，并将tdata复制到复制到x。岔届享娩柳彭遗哭姚搅婪抉痴潦旋议耶郝伤逐经沃缕丸狭汐苫物挛投睛运高级数据结构高级数据结构285JYP 由由于于当当前前C中中已已有有关关键键字字一一定定大大于于新新加加入入部部分分的的关关键键字字，所所以以新新加加入入部部分分应应作作为为当当前前C中中最最小小关关键键字所在结点（用字所在结点（用L指向）的左子树，如下所示：指向）的左子树，如下所示：查皱担扒诚坠秒酷嗅侍哥抵救援弯镁附拟立社济爱枷具触类渴咕赡句刁四高级数据结构高级数据结构286JYP 同同理理，新新加加入入B部部分分应应作作为为当当前前B中中关关键键字字最最大大元素所在结点（用元素所在结点（用R指向）的右子树。指向）的右子树。 为为了了避避免免判判断断树树为为空空的的情情况况，在在开开始始时时为为B和和C分别引入头结点分别引入头结点Y和和Z。下面是实现分裂操作的算法：。下面是实现分裂操作的算法：template Element* BST:Split(Type i, BST&B, Element&x, BST&C) / 根据关键字i分裂 if (!root) B.root = C.root = 0; return 0; / 空树 BstNode *Y = new BstNode; / B的头结点 BstNode *R = Y; BstNode *Z = new BstNode; / C的头结点 BstNode *L = Z;斑脖会闺馋叼妄后卜贬检躁膊钵述仁塑递帘救雄任磺戚次婶瑶泊秃氮劝诞高级数据结构高级数据结构287JYPBstNode *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 &x; else if (i tdata.key) LLeftChild = t; L = t; t = tLeftChild; 汇东役留役俞肥幂热职烘柔气影惫陷猛纷禾舷辩暗磁苯衔贸庚釉赐坯突奄高级数据结构高级数据结构288JYP else RRightChild = t; R = t; t = tRightChild; RRightChild = LLeftChild = 0; / 注意这是必要的 B.root = YRightChild; delete Y; / 删除头结点 C.root = ZLeftChild; delete Z; / 删除头结点 root = 0; return 0; 卸搞滚刊商葱膛瓢迂菊腺料禽玛则伍郧眶房掺晨畦夷唁阅碑约械秀促邻硅高级数据结构高级数据结构289JYP 对对Split的的分分析析：while循循环环始始终终保保证证以以t为为根根的的子子树树中中的的所所有有关关键键字字大大于于正正在在构构造造的的B中中关关键键字字，小小于于正正在在构构造造的的C中中的的关关键键字字。由由此此容容易易证证明明算算法法的的正确性。正确性。 算算法法的的时时间间复复杂杂性性是是O(height(A)。B和和C的的高高度度不超过不超过A的高度。的高度。寺染总子盼滤编傻戌矣眼役潜澄杆挛畴残窝谭刻热衙董蝉相外乍谬皖切晶高级数据结构高级数据结构290JYP二叉查找树的性能分析二叉查找树的性能分析 （8.2.4） 为为了了分分析析二二叉叉查查找找树树的的性性能能，再再次次引引用用扩扩展展二二叉叉树的概念，即用方结点替代所有空二叉子树。树的概念，即用方结点替代所有空二叉子树。 这些方结点又称为外部结点。这些方结点又称为外部结点。 二叉树原来的（圆）结点称为内部结点。二叉树原来的（圆）结点称为内部结点。秉靖拳良避得笆系柞澜书团隐瓣硝术丛筐左涅孪诗普菠沸衍肠拦过口崔沫高级数据结构高级数据结构291JYP 图图8.1（b）的扩展二叉树如下所示：）的扩展二叉树如下所示：追和铲抚镣寻篡丫拯腔并啸但娶碰鸯紫导蛔锥昏粉阜第掸虱驳阐恋晋酱囊高级数据结构高级数据结构292JYP n个结点的二叉树有个结点的二叉树有n + 1个外部结点。不成功的个外部结点。不成功的查找都会在某一个外部结点结束，所以也称外部结查找都会在某一个外部结点结束，所以也称外部结点为点为失败结点失败结点。 二叉树的二叉树的外部路径长度外部路径长度E定义为所有外部结点到定义为所有外部结点到根结点的路径长度之和。根结点的路径长度之和。 内部路径长度内部路径长度I是所有内部结点到根结点的路径是所有内部结点到根结点的路径长度之和。长度之和。 图图8.6的内部路径长度是的内部路径长度是 I = 0 + 1 + 1 + 2 = 4其外部路径长度其外部路径长度E是是 E = 2 + 2 + 2 + 3 + 3 = 12丧顿糜奥傲准胁氧筑椅光烷卤学海渊灌庄苍蹿本典歌倒可卓饯基计稻他袋高级数据结构高级数据结构293JYP 引理引理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到根结点的路径长度。到根结点的路径长度。流伯膏焉夜柳脾漆弊祟敝统郡亦宽渊腐航塔层仍篓锹考烟韩患阵夫伪携宝高级数据结构高级数据结构294JYP 将将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也成立。也成立。 铰颓凸抓狞赶崔趣收样澎婿蛊达刽邮那头牲抛碌墙采我轰墓缉挠彭读弹熊高级数据结构高级数据结构295JYP 查找二叉查找树的时间依赖于所考察的内部结点查找二叉查找树的时间依赖于所考察的内部结点个数，假设一个内部结点的计算时间用个数，假设一个内部结点的计算时间用一次比较一次比较度度量，下面分析具有量，下面分析具有n个内部结点的二叉查找树的性能。个内部结点的二叉查找树的性能。抽邹月类案吕感鸯韶蒲拒瓷猿隧写辆历附篓撒拣酣缺激琢淘羌核稍箱寿异高级数据结构高级数据结构296JYP1 最坏情况最坏情况 根据引理根据引理8.1，具有最大，具有最大I的扩展二叉查找树也具的扩展二叉查找树也具有最大的有最大的E。 在二叉树完全偏斜时在二叉树完全偏斜时I达到最大值。这时，达到最大值。这时， I = = 因此，在最坏情况的二叉查找树中进行成功查找因此，在最坏情况的二叉查找树中进行成功查找的平均比较次数的平均比较次数Sn为为 Sn = = (8.1)携展挥驹总秆骏袖愚咽悯瞳碎述惑轰兹惶害紊鞍器崇迟艇瑶紊减理蒲铀韩高级数据结构高级数据结构297JYP2 最好情况最好情况 为了使为了使I最小，应使尽可能多的内部结点靠近根最小，应使尽可能多的内部结点靠近根结点。在与根结点的距离为结点。在与根结点的距离为1处最多可有处最多可有2个结点，个结点，距离为距离为2处最多可有处最多可有4个结点，一般地，最小的个结点，一般地，最小的I是是 0 + 2 1 + 4 2 + 8 3 + + 完全二叉树就是一种具有最小内部路径长度的树。完全二叉树就是一种具有最小内部路径长度的树。采用完全二叉树的结点编号，结点采用完全二叉树的结点编号，结点i到根结点的距离到根结点的距离是是 log2i 。这样，最小的。这样，最小的I是是 I = 牢砒瘟马云量卷谤衰兜备衷的笔梅耪允内府雅牵陈剥刨熊叙互嘲凝信护睫高级数据结构高级数据结构298JYP 利用数学推导可得：利用数学推导可得： = (n + 1)q 2(q + 1) + 2， 其中，其中，q = log2(n + 1) 因此，在最好情况的二叉查找树中进行成功查找因此，在最好情况的二叉查找树中进行成功查找的平均比较次数的平均比较次数Sn为为 Sn = = log2(n + 1) 1 log2n1 (8.2)因丽计驮戈取顿女咽神棱获纠扯绞持淌卯栖黄院上璃镑吝岂客拱侵劈夹搁高级数据结构高级数据结构299JYP 3 平均情况平均情况 Sn 平均成功查找所需的比较次数平均成功查找所需的比较次数 Un 平均不成功查找所需的比较次数平均不成功查找所需的比较次数 在树中查找到任何关键字所需的比较次数正好是在树中查找到任何关键字所需的比较次数正好是含该关键字的元素首次插入所需的比较次数加含该关键字的元素首次插入所需的比较次数加1，而，而插入该元素所需的比较次数与该元素不在树中的不插入该元素所需的比较次数与该元素不在树中的不成功查找的相同。成功查找的相同。 该元素不在树中的不成功查找等概率地出现在树该元素不在树中的不成功查找等概率地出现在树中含中含0, 1, , n 1个结点的情况。由此可得：个结点的情况。由此可得： Sn = 1 + 衰汇辞瞥斗寨搽良桨相臃抖咐掐尘城柴夏辖肖趁睡浓酬蹈僧淘犹缨蔫炎达高级数据结构高级数据结构300JYP同时，同时，Sn = ，Un = ，E = I + 2n，所以，所以， Sn = = 即即 Sn = Un 1(8.3)兑车抓蘑界茄泞爽宏扬戍搜掷勉笑费厚啊最溪哇消帜镇灸魔秃洞沿恨旗富高级数据结构高级数据结构301JYP又由又由 Sn = 和和 Sn = 1 + 可得可得 I = U0 + U1 + + Un-1再由再由 Un = = 可得可得痞亨搬的足长靛抛儡缴片淆遂镀拳砒姥栗锤裔宫滁董勃贬棍码褪缓壮逆务高级数据结构高级数据结构302JYP(n + 1)Un = 2n + U0 + U1 + + Un-1为解此递归式，用为解此递归式，用n 1替换替换n：n Un-1 = 2(n 1) + U0 + U1 + + Un-2两式相减，得：两式相减，得：Un = Un-1 + 赴绍捷掳无飞膘姓挺诀盂论消瑞狠缎径巍纳掀辅殿冉客律绿筐肿獭衙摆蝇高级数据结构高级数据结构303JYP由于由于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)冕差表苯畸天幂拔漂款垛葱撼枷乔口发谨怪淋勘啡弹肠桌序抚蛛浦起脑腆高级数据结构高级数据结构304JYP由由(8.3)式，式， Sn 1.39 log2n 1。签忍吉湖惕痢你惊撤姆妊揩灿具柏达陆薛泡昔错堤生厚柑突蓖骇萄块拓赚高级数据结构高级数据结构305JYP最佳二叉查找树最佳二叉查找树 （8.2.5） 如果一个符号表固定，只对其进行查找操作，则如果一个符号表固定，只对其进行查找操作，则称其为称其为静态符号表静态符号表。 电子词典就可以看成是一个静态符号表，且在实电子词典就可以看成是一个静态符号表，且在实际应用中人们对不同单词的查找概率是不同的。际应用中人们对不同单词的查找概率是不同的。 下面讨论表示静态符号表的二叉查找树的构造问下面讨论表示静态符号表的二叉查找树的构造问题。题。 当查找各标识符的概率相同时，可以用最好情况当查找各标识符的概率相同时，可以用最好情况二叉查找树表示该符号表。二叉查找树表示该符号表。少诺壹扑蜜奠诀毛合猎佯淆辫剑过笛选校昆昨约锨教岁被母瞪浑姓帆沼感高级数据结构高级数据结构306JYP 当查找各标识符的概率不相同时，完全二叉树不当查找各标识符的概率不相同时，完全二叉树不一定是最佳的。一定是最佳的。 直觉上，查找概率越大的标识符越靠近根结点性直觉上，查找概率越大的标识符越靠近根结点性能越好。能越好。 这就要求我们为标识符查找概率不相同的符号表这就要求我们为标识符查找概率不相同的符号表构造构造最佳二叉查找树最佳二叉查找树。 设需要构造的二叉查找树包含标识符设需要构造的二叉查找树包含标识符a1, a2, , an，且，且a1 a2 an，查找每个，查找每个ai,的概率是的概率是pi，则，则当查找只限于成功情况时，该二叉查找树的代价是当查找只限于成功情况时，该二叉查找树的代价是蜜置呈痰囊稍才芍仓作敏九蹋桂因致郴藻美素苹哇乡腿在蹦品辟鹤骚格据高级数据结构高级数据结构307JYP 不不成成功功查查找找在在算算法法Search检检查查到到失失败败结结点点时时结结束束。不不在在二二叉叉查查找找树树中中的的标标识识符符可可被被划划分分为为n+1个个类类Ei，0in。 E0包包含含所所有有满满足足x a1 的的标标识识符符x，Ei包包含含所所有有满满足足ai x ai+1的的标标识识符符x，1i an的标识符的标识符x。 对对于于Ei中中的的所所有有标标识识符符，查查找找都都会会在在同同一一个个失失败败结结点点结结束束，且且对对于于不不同同类类中中的的标标识识符符，查查找找会会在在不不同的失败结点结束。同的失败结点结束。 将将失失败败结结点点从从0到到n编编号号，编编号号i的的失失败败结结点点对对应应Ei，0in。呕麻瞒插悠砍剁赛豁崭胸叙咕脉僳句诈残稽铡啪寞扬滦纵锨元喧蜜寞涟惫高级数据结构高级数据结构308JYP 设设qi是是所所查查找找的的标标识识符符属属于于Ei的的概概率率，则则全全部部失失败结点的代价是败结点的代价是 该二叉查找树的总代价是该二叉查找树的总代价是(8.5) 表示表示a1, a2, , an的最佳二叉查找树应使的最佳二叉查找树应使(8.5)式的值最小。式的值最小。班害施司银绦侈着尹闸邀巷韩边岭颇焊蛋破阳姿毗烤翌全煌梗力由险并咬高级数据结构高级数据结构309JYP 例例8.1 图图8.8给出了用于表示给出了用于表示a1, a2, a3 = (data, pipe, work)的所有可能的二叉查找树：的所有可能的二叉查找树：纠桂念烟单奥漓聋勾崩末斗效画群腰韧去玻检侯讲哀扫钻捡忠苹贰笆配因高级数据结构高级数据结构310JYP弗矽菲拥臃赤嘻圭莱店贮专钥咬膀河痔蛀笺幼诈皱留诺魏傲屁愿编瘪蓬福高级数据结构高级数据结构311JYP 当当pi = qj = 1/7时，时，1i3，0j3，有，有 树（树（a）的代价）的代价 = 15/7 树（树（b）的代价）的代价 = 13/7 树（树（c）的代价）的代价 = 15/7 树（树（d）的代价）的代价 = 15/7 树（树（e）的代价）的代价 = 15/7 正如可以预料到的，树（正如可以预料到的，树（b）是最佳的。）是最佳的。仔碳赘龄徽羊昂散陷诲仰拄棋暂摔鲍银亡贩感呀薄工龟薄蝉畔法祁秃倦惫高级数据结构高级数据结构312JYP 当当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）是最佳的。）是最佳的。匿专腻言离佑饮梢铆沁桩悄瓦矫您丹宏靡悲壕缎洛容岗反系访幻帝今客蓖高级数据结构高级数据结构313JYP 采采用用例例8.1的的穷穷举举方方法法确确定定代代价价最最小小的的树树计计算算复复杂杂性很高。当性很高。当n较大时，这种方法是没有实用价值的。较大时，这种方法是没有实用价值的。 通通过过利利用用最最佳佳二二叉叉查查找找树树的的一一些些性性质质，则则可可以以得得到相当高效的算法。到相当高效的算法。 设设Tij表表示示包包含含ai+1, , aj（i j）的的最最佳佳二二叉叉查查找找树树，则则Tii（0in）是是空空树树，且且对对于于j i，Tij无无定定义。义。 设设cij为为Tij的代价。由定义，的代价。由定义，cii = 0。 设设rij为为Tij的根结点标识符的下标号。的根结点标识符的下标号。绅花卢美踊猛笋为铃肪而阳默咳衅这漫崇井郸淌仅禹撕讯擂诲间芭屏艇奈高级数据结构高级数据结构314JYP 再设再设wij = qi + 为为Tij的权重。由定义，的权重。由定义，wii = qi，0in。 于是，于是，T0n是包含标识符是包含标识符a1, a2, , an的最佳二叉的最佳二叉查找树，其代价是查找树，其代价是c0n，其根结点标识符的下标是，其根结点标识符的下标是r0n。倦纵微途乾卿区扳连曝坠犁嗣妄齐睫振屁小妙锚舶底胆倔再螟莽扛啄鸿碗高级数据结构高级数据结构315JYP 如如果果Tij是是包包含含ai+1, , aj的的最最佳佳二二叉叉查查找找树树，且且rij = k，则则i kj。Tij有有左左、右右两两棵棵子子树树，如如下下图图所所示：示：哮箱绝由孺臭阜全灌肉渝丁鞠苏癌奇竞境锨淌姿卒掩耶审顿单鸳详倔箍酪高级数据结构高级数据结构316JYP 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)仿您胰碱职巳推惰烧债怔蔷揪馈诧膏菜俏初旱屏升轿寄荣灌亢榷未钦敖维高级数据结构高级数据结构317JYP 由于由于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。郑炯嗅舒汇谱稼煮驻克纫浑蚜腆笺腹蒲翱耽器障酷挞辕广汽跃派椭镣蛛雷高级数据结构高级数据结构318JYP 例例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镁办禽忘锰莫蒂愁琳哨蹈焦渍侵屁之稠放矮瀑仲檬先划蜜鼻鹅粮昼玄脖科高级数据结构高级数据结构319JYP 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给出了此计算结果。给出了此计算结果。 哪熬棱锌驻视熙轮皇锄庇缀盔栏蛔抨法涨傈完箱莲掉忙桓僳乘君挎瘴褐扒高级数据结构高级数据结构320JYP皿结枝毒叹犊大滴谅芝喻绥旺斑狈亩耍裙澎车衬躁护倚撬宾屈闹坟郑毕煌高级数据结构高级数据结构321JYP 由此，由此，c03 = 1.55是最小代价，是最小代价，T03的根结点含标识符的根结点含标识符a1，其左子，其左子树是树是T00，右子树是，右子树是T13。 T13的根结点含标识符的根结点含标识符a3，其左，其左子树是子树是T12，右子树是，右子树是T33。 T12的根结点含标识符的根结点含标识符a2，其左，其左子树是子树是T11，右子树是，右子树是T22。由此可。由此可以构造以构造T03，如右图所示。，如右图所示。绪嫂呼辙虹中蚌骡逞池肛慑磨产学坟呈茁狸衡呐绅阿苹倒找泪捍货谴妖谐高级数据结构高级数据结构322JYP 由于本例子中假设的由于本例子中假设的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)。颇乐炸患耗稠蛛滔瞄胸颠肚烽承弗乙鞘卉三睛州氦人合珐胎兜馋羹堪诅炒高级数据结构高级数据结构323JYP 计算全部计算全部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) 恼剐末有犁韧凯绣呢极筋矫久临遣脖痞扭哥砖反扇琴魔愤是慢裔蛤诞始远高级数据结构高级数据结构324JYP 当当j i = m，且，且m = 1时的总计算时间为时的总计算时间为n m + 1。计算全部计算全部cij和和rij的总时间改进为的总时间改进为 n m + 1 + = O(n2) 假假设设二二维维数数组组w、c和和r是是类类BST的的私私有有数数据据成成员员。算算法法obst实实现现了了上上述述方方法法，并并根根据据计计算算结结果果调调用用函函数数build构造最佳二叉查找树。构造最佳二叉查找树。耸粤乳蔫鹊原辐伍衣励呸套佛蚜蕊瘤黄童拾氯鄂泄插没趁患引摔土剁瞻甸高级数据结构高级数据结构325JYPtemplate 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;稀央汾斥誉诬阉乃居狗女苯题揽颁摸韦忙鱼澄嘿荔甫芳雁榔增管钟诚烽吮高级数据结构高级数据结构326JYP 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结束年禹炙戚凌柱桶齿默眉姬拆叙沉荣幌远旧纺寂电织栈屿潦拽慌宜踏艾敬别高级数据结构高级数据结构327JYPtemplate 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)。峦毖修卢蝎嫡戴砸栈员鹊敢觉铜砍谤瞳颂耗诅烛喊菇诫滴法拣垢盒钓绽挖高级数据结构高级数据结构328JYP8.6.6 B+树树 B树只有利于单个关键字查找，而在数据库等许树只有利于单个关键字查找，而在数据库等许多应用中常常也需要范围查询。多应用中常常也需要范围查询。 为了满足这种需求，需要改进为了满足这种需求，需要改进B树。树。 B+树就是这种改进的结果，也是现实中最常用的树就是这种改进的结果，也是现实中最常用的一种一种B树变种。树变种。 B+树与树与B树的最大树的最大区别是区别是：B+树的元素只存放在树的元素只存放在叶结点中。叶结点中。 不是叶的结点又称为不是叶的结点又称为中间结点中间结点。中间结点也存放。中间结点也存放关键字，但这些关键字只起引导查找的关键字，但这些关键字只起引导查找的“路标路标”作作用。用。炒选故褐华哥芝沪气磅谤审由告供臆崔常驴漆岗洗晌怀俯浸金钱曲惦挂匠高级数据结构高级数据结构329JYP 定义：定义：一棵一棵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。怪删止欠揪饲度蛊怠女万己铲裂疯玲毁支引国锚散恫庄体识安撩郝海楔辟高级数据结构高级数据结构330JYP（4） An中的所有关键字都大于等于中的所有关键字都大于等于Kn，A0中的所中的所有关键字都小于有关键字都小于K1。（5） 根结点至少有根结点至少有2棵子树，其它中间结点至少有棵子树，其它中间结点至少有 m/2 棵子树。棵子树。（6） 所有叶结点都处于同一个层次，包含了全部所有叶结点都处于同一个层次，包含了全部关键字以及相应的元素或元素地址，叶结点中的关关键字以及相应的元素或元素地址，叶结点中的关键字从小到大排序，且互不相同。键字从小到大排序，且互不相同。（7） 叶结点中存放的关键字个数可以大于或小于叶结点中存放的关键字个数可以大于或小于m。设。设mleaf是叶结点可容纳的最大失败结点个数，是叶结点可容纳的最大失败结点个数，则其中的实际关键字个数则其中的实际关键字个数n应满足：应满足：1 mleaf/2 1n mleaf。 摇翟卤虐现兽辜大只刑炊拴顿邢痛等玻弹彩逃废辽烹贷鼓吃褐幂激狂兢林高级数据结构高级数据结构331JYP B+树的叶结点被链接成双链表，以便范围查询。树的叶结点被链接成双链表，以便范围查询。 图图8.30是一个是一个B+树的例子：树的例子：其其中中，m=3，mleaf=5。以以后后的的例例子子都都假假设设m=3，mleaf=5。 练堑碟醒坪慧胃坡吗郝地滴判癣别动搀谆铬谢浦筑或咬楼恳熄琉唱溯挫洛高级数据结构高级数据结构332JYP 除了需要一直查到叶结点以外，除了需要一直查到叶结点以外，B+树的树的查找查找方法方法与与B树的基本相同。树的基本相同。 即使中间结点中已有需要查找的关键字，但那也即使中间结点中已有需要查找的关键字，但那也只是只是“路标路标”，并不提供实际元素的地址。，并不提供实际元素的地址。 例如，在图例如，在图8.30中查找中查找35。35在根结点中，表示在根结点中，表示关键字为关键字为35的元素在第的元素在第2棵子树中。由根结点的第棵子树中。由根结点的第2棵子树的第棵子树的第1个分枝，可到达关键字为个分枝，可到达关键字为35的元素所在的元素所在的叶结点。的叶结点。超契汉吨包险券愤设毗罗军怜釜副剁撤员稽写禹捻霍根裕奥和核呜陋播攫高级数据结构高级数据结构333JYP 往往B+树中树中插入插入关键字为关键字为x的元素的方法与的元素的方法与B树的树的类似。类似。 首先，定位到关键字为首先，定位到关键字为x的元素可插入的叶结点的元素可插入的叶结点p。 如果结点如果结点p不满，则加入新元素，并将修改后的不满，则加入新元素，并将修改后的结点结点p写到磁盘即可。写到磁盘即可。 如果结点如果结点p已满，则将其分裂为已满，则将其分裂为p和和q两个结点，两个结点，这两个结点平均承载原来结点这两个结点平均承载原来结点p中的内容和新元素，中的内容和新元素，且结点且结点q中元素的关键字大于结点中元素的关键字大于结点p中的。再将结点中的。再将结点q中最小关键字和指针中最小关键字和指针q插入结点插入结点p的双亲。的双亲。啸屡耿具绽摧嫡嗽蘸烦鹅蜜炙楞匿叼罗岸里琐事励拒怀喻峨爷恕起离沁兜高级数据结构高级数据结构334JYP 这又可能使双亲结点分裂，直至使根结点分裂，这又可能使双亲结点分裂，直至使根结点分裂，整个整个B+树长高一层。树长高一层。 图图8.31通过例子描述了上述插入过程，其中，中通过例子描述了上述插入过程，其中，中间结点的粗体字表示新插入的间结点的粗体字表示新插入的“路标路标”，叶结点的，叶结点的粗体字表示新插入的关键字。粗体字表示新插入的关键字。饭废铺椽腔澎吭豪兜凶屏准筑首栗件烦瞳领墒效肛若桑迁赡邑曙惑耪性酸高级数据结构高级数据结构335JYP图图8.31 1衷炔挟勇泼蜗蹬帅拒卓葫蒂捧兄憨晒恳颧菏甘芳衔斜条吠钒屏粒愧甚骄澄高级数据结构高级数据结构336JYP图图8.31 2脱蹿乌绪涝蝶缔下拂侩油踏迟使峡大肪谓博底屎巍诽予讣唐战枪效陌衷胆高级数据结构高级数据结构337JYP 从从B+树中树中删除删除关键字关键字x的方法也与的方法也与B树的类似。树的类似。 首先，定位到关键字首先，定位到关键字x所在的叶结点所在的叶结点p。 如如果果删删除除后后结结点点p中中的的关关键键字字个个数数仍仍然然大大于于等等于于 mleaf/2 1，则将修改后的结点，则将修改后的结点p写到磁盘即可。写到磁盘即可。梁晤酉猾响窜蹄眼条毙蠕蒸滔谩汽痊掂气甩义柏痊符篇隔楼能落襟雌缀蓬高级数据结构高级数据结构338JYP 例如，从图例如，从图8.30的的B+树中删除树中删除30，服盲调蛰苯模搭惕张厢闹刃葛软痔弯碴粘卵纸猪按瞪刃妨纶鸟稼傀谢极酥高级数据结构高级数据结构339JYP得得到到图图8.32的的B+树树。注注意意，虽虽然然元元素素30已已被被删删除除，但作为但作为“路标路标”的的30不必从中间结点中删除。不必从中间结点中删除。脐志友蝗劳提魄筷躬邵艾赋驴型提嘴凳闪陆冗堡罚弟阐趣驳忙剖崎艺祟体高级数据结构高级数据结构340JYP 如如果果删删除除后后结结点点p中中只只有有 mleaf/2 2个个关关键键字字，且且其其最最邻邻近近兄兄弟弟q至至少少有有 mleaf/2 个个关关键键字字，则则可可从从结结点点q移移一一个个到到结结点点p，从从而而使使这这两两个个结结点点都都满满足足要要求。求。 此此过过程程还还需需要要改改变变双双亲亲结结点点中中的的“路路标标”，以以反反映结点映结点p或或q中第一个关键字的值。中第一个关键字的值。抿片悉进命泣粘差厚疫砷晶也吾力侄妓殴厨纷态托秘哪蹋伙芝炽梦关狠萌高级数据结构高级数据结构341JYP 例例如如，从从图图8.32的的B+树树中中删删除除31，使使得得第第2个个叶叶结结点点中中的的28被被移移来来替替代代其其原原来来的的位位置置，得得到到图图8.33的的B+树。树。傲饰熟瘟驶盅彬腔似灼苇汉绢呜速姬删漠闸迢基多匙塑渣则失沈撑殿悲失高级数据结构高级数据结构342JYP 如如果果删删除除后后结结点点p中中只只有有 mleaf/2 2个个关关键键字字，且且其其最最邻邻近近兄兄弟弟q只只有有 mleaf/2 1个个关关键键字字，则则需需要将结点要将结点q的内容合并到结点的内容合并到结点p，并删除整个结点，并删除整个结点q。 这这又又可可能能导导致致双双亲亲结结点点关关键键字字个个数数不不足足，引引起起新新一轮的旋转与合并，直至删除根结点。一轮的旋转与合并，直至删除根结点。拄愉臼竭失碉重逢淡算耸空受舱吁椰邯坛他禾煞肛皂韵噶缩蔓疽每卞筷伍高级数据结构高级数据结构343JYP 图图8.34描描述述了了从从图图8.33的的B+树树中中删删除除35的的过过程程，注注意意，“路路标标”28移移到到根根结结点点，35移移到到根根结结点点的的右右子女。子女。图图8.34 1福岂狱巢叶蔡轨神椭皆耕删捅堂杂绸氯旷攻榷何狈遇会瞬组炼品扛典恒豢高级数据结构高级数据结构344JYP图图8.34 2档组梨柔脂诲涨理英隋殴练爷宁贼终搞赤蕴葫凭医诛键丫懈霸象翔止港熄高级数据结构高级数据结构345JYP实验作业实验作业： 设设计计一一个个磁磁盘盘资资源源管管理理系系统统，实实现现B+树树的的查查询询、插插入入和和删删除除操操作作，并并生生成成测测试试数数据据集集，验验证证这这些些操操作的正确性。作的正确性。朵牡肩尤玩抖垃护艺敦层胚缘盈蘑往砰捣绩狮榔幕空罗明肋虏疤否哗益藻高级数据结构高级数据结构346JYP动态散列动态散列 （8.9） 静态散列必须静态分配散列表空间。静态散列必须静态分配散列表空间。 如果分配的表空间过大，则会浪费空间；如果分如果分配的表空间过大，则会浪费空间；如果分配的表空间过小，则会导致冲突频繁，而且当数据配的表空间过小，则会导致冲突频繁，而且当数据量大于散列表的容量时整个散列表需要重组。量大于散列表的容量时整个散列表需要重组。 动态散列动态散列又称为又称为可扩展散列可扩展散列，其目的就是要既保，其目的就是要既保持静态散列的快速查找性能，又具备动态适应数据持静态散列的快速查找性能，又具备动态适应数据文件大小变化的能力。文件大小变化的能力。 假设文件假设文件F是记录是记录R的集合。每个记录有一个关的集合。每个记录有一个关键字键字key。记录存储在。记录存储在页面页面（或桶）中，每个页面的（或桶）中，每个页面的容量是容量是p个记录。个记录。暗溯抓涕莹哆犯郝味素颧寐吾彼现膏藐罕翌松杠文傲壶蛆桔簿代屠蛹赘捉高级数据结构高级数据结构347JYP 在设计算法时，应尽量减少对页面的访问次数，在设计算法时，应尽量减少对页面的访问次数，因为页面通常存储在磁盘上。因为页面通常存储在磁盘上。 空间利用率空间利用率定义为定义为n/(mp)，其中，其中，n是记录个数，是记录个数，m是页面数。是页面数。 蚁非砖螟品奎华饺阔茵官缺示劣掌六伤难恶障燎差债受资殷慨彻印芜生庄高级数据结构高级数据结构348JYP8.9.1 带目录动态散列带目录动态散列 每每个个关关键键字字由由一一个个二二进进制制编编码码表表示示。给给定定一一个个散散列列表表ht，关关键键字字x在在ht中中的的位位置置可可通通过过其其编编码码的的k个个最低二进制位确定。最低二进制位确定。 目目录录实实际际上上是是一一个个散散列列表表，该该表表的的每每个个目目录录项项存存放一个页面指针。放一个页面指针。 如如果果用用k个个二二进进制制位位区区分分关关键键字字，则则目目录录有有2k个个目录项，分别对应下标目录项，分别对应下标0, , 2k1。 查查找找关关键键字字x时时，用用与与x的的最最低低k个个二二进进制制位位对对应应的整数定位目录项，再搜索该目录项指向的页面。的整数定位目录项，再搜索该目录项指向的页面。兴金穷怪睹宽抨寡薯盼耪畔竟砂郴蚁瘤拔许舶讣蹋魏酮胃帮老筛语每法敏高级数据结构高级数据结构349JYP 下面通过一个下面通过一个例子来观察目录例子来观察目录的动态扩展过程。的动态扩展过程。 假设关键字由假设关键字由2个字符组成，每个字符组成，每个字符由个字符由3个二进个二进制位表示。制位表示。 右图是一些关右图是一些关键字及其二进制键字及其二进制表示。表示。孽口舞恬文悍岩桐庞鲤虎躇婚屈煎赚蓄鸟蝇浸暖玻钙滥称限僳认兴健峰扭高级数据结构高级数据结构350JYP 假设初始时目录有假设初始时目录有4项。每个页面可容纳项。每个页面可容纳2个记录。个记录。需用关键字的需用关键字的2个最低位来确定目录项。个最低位来确定目录项。 将关键字将关键字A0, B0, C2, A1, B1和和C3加入表中后的结加入表中后的结果如下图（果如下图（a）所示：）所示：喇溃棒盖溉辑支挑敬吟站鲁涪彩峡许趣颧茁敬放鹿嘉沛蜕牲屹敞硕小谚润高级数据结构高级数据结构351JYP 再将再将C5加入表中。加入表中。由于由于C5的的2个最低位个最低位是是01，因此应存入页，因此应存入页面面b。但。但b已满，从而已满，从而发生溢出。发生溢出。 这时新增加一个页这时新增加一个页面面e，同时改用，同时改用3个最个最低位区分关键字，并低位区分关键字，并使目录的目录项数扩使目录的目录项数扩大一倍，如右图（大一倍，如右图（b）所示。所示。任镊凛札疫驮页义戮堂孙症沼跨屏可献娠舟哗霓闯釉感鲸叛哺逢畔遵喊佬高级数据结构高级数据结构352JYP 观察图（观察图（b），虽然整个散列表需要），虽然整个散列表需要3个最低二进个最低二进制位确定关键字所在页面，但实际上不是所有页面制位确定关键字所在页面，但实际上不是所有页面都需要都需要3个最低二进制位来确定。个最低二进制位来确定。 例如页面例如页面a被被2个目录项指向，且我们实际只需要个目录项指向，且我们实际只需要2个最低位即可确定其中关键字所在页面。因为个最低位即可确定其中关键字所在页面。因为a中中关键字的关键字的2个最低位是个最低位是00，在，在00前面加上前面加上0或或1得到得到000或或100，由此对应的，由此对应的2个目录项都指向页面个目录项都指向页面a。 如果对于一个页面内的关键字，实际只需要如果对于一个页面内的关键字，实际只需要i个最个最低位即可确定其所在页面，则称该页面的低位即可确定其所在页面，则称该页面的局部深度局部深度为为i。 在整个散列表中，所有局部深度的最大者称为在整个散列表中，所有局部深度的最大者称为全全局深度局深度。患渭扭勿佰绚惕蹬简课旭恳框纪膳新观载哮挚坚檬蜡查举瞧硒松苑脏突杠高级数据结构高级数据结构353JYP 在图（在图（a）中，每个页面只被）中，每个页面只被1个目录项指向，全个目录项指向，全局深度为局深度为2。 在图（在图（b）中，页面）中，页面b和和e分别只被分别只被1个目录项指向，个目录项指向，局部深度为局部深度为3；其余页面都被；其余页面都被2个目录项指向，局部个目录项指向，局部深度为深度为2；全局深度为；全局深度为3。 衔些言扰渊董均捶弦搐猩羌瘴擞被扦埋慎烬枕撞冕握颤催映恫衙有德舀聚高级数据结构高级数据结构354JYP 访问任何页面都需要两个步骤：访问任何页面都需要两个步骤：（1）通过散列函数确定目录项，并得到页面地址；）通过散列函数确定目录项，并得到页面地址；（2）访问该页面。）访问该页面。 如果关键字在页面中的分布不均匀，目录增长可如果关键字在页面中的分布不均匀，目录增长可能过大，而大多数目录项都指向同一页面。能过大，而大多数目录项都指向同一页面。 为防止这种情况，不宜直接使用关键字的二进制为防止这种情况，不宜直接使用关键字的二进制位序列，而应通过均匀散列函数将这些二进制位转位序列，而应通过均匀散列函数将这些二进制位转换为随机序列。换为随机序列。铆市淮禹冉辟睁拍楞烂琅壹昂憋阎睁疡杠诱述桅球刀笼族瞻漱俯好茫鼎驻高级数据结构高级数据结构355JYP 还需要一个还需要一个散列函数簇散列函数簇，因为在整个表动态变化，因为在整个表动态变化的不同时刻，需要不同的二进制位个数来区分关键的不同时刻，需要不同的二进制位个数来区分关键字。字。 以下是一种解决方案：以下是一种解决方案：hashi: key 0, , 2i 1，1id其中，其中，hashi的结果只是简单地在的结果只是简单地在hashi-1的结果前端的结果前端加上二进制位加上二进制位0或或1。 因此，散列函数因此，散列函数hash(key, i) 根据关键字根据关键字key生成生成一个与一个与i个二进制位对应的随机数。个二进制位对应的随机数。经唯挑民毙橇晓峨靴咬申吼涩疽齿弯痴摹铝哗户弹莉缓羔番个控峪磷批闻高级数据结构高级数据结构356JYP 当局部深度为当局部深度为i的页面溢出时，分配一个新页面，的页面溢出时，分配一个新页面，并将关键字重新散列到这两个页面。并将关键字重新散列到这两个页面。 这两个页面中的关键字的这两个页面中的关键字的i个最低位相同，称它们个最低位相同，称它们为为伙伴伙伴。 当两个伙伴页面中的关键字个数不大于一个页面当两个伙伴页面中的关键字个数不大于一个页面的容量时，就将这两个页面的容量时，就将这两个页面合并合并，释放多余的页面，释放多余的页面，并将结果页面的局部深度减少并将结果页面的局部深度减少1。 假设需要向一个局部深度为假设需要向一个局部深度为i，容量为，容量为p且已经包且已经包含含p个记录的页面加入一个新记录，则先从操作系统个记录的页面加入一个新记录，则先从操作系统获得一个新页面。获得一个新页面。误悍茂叫舞险瑟陵些计论谋恩涤遭瓶绘恳圈惜洁臼碉臻棉问擅债京仓办颧高级数据结构高级数据结构357JYP 利用利用i + 1个二进制位将个二进制位将p + 1个关键字重新散列到个关键字重新散列到这两个页面，并将这些页面的局部深度设置为这两个页面，并将这些页面的局部深度设置为i + 1。 如果如果i + 1大于全局深度，则整个目录增长一倍，大于全局深度，则整个目录增长一倍，全局深度加全局深度加1。 如果所有如果所有p + 1个关键字被散列到两页面之一，则个关键字被散列到两页面之一，则上述分裂过程还须继续。上述分裂过程还须继续。杆忽迢疯几搽酣笨桌备宅锁懈堆壮痹布灌牵沧漫灯辑踊辩沁温旦卫刺瓦溪高级数据结构高级数据结构358JYP 以下程序给出了实现带目录的动态散列的概要性以下程序给出了实现带目录的动态散列的概要性描述：描述：template struct record / 记录结构 Type key; / 其它数据字段;template struct page / 页面结构 record namesPageSize;/ 假设PageSize是已定义的常数 int NumRecords;/ 本页面的记录个数;感厅衙望惶矽缀揉倔路饶香懂苑再鸯袱讽丽吝踪拷遣次躺绸酚妙獭锈滦扁高级数据结构高级数据结构359JYPtemplate struct DirEntry / 目录项结构 int LocalDepth;/ 该目录项所指页面的局部深度 page* paddr; / 注意这是用指针模拟页面地址;template DirEntry rdirectoryMaxDir; / 目录，假设MaxDir是已/ 定义的常数int gdepth;/ 全局深度，要求1gdepthKeySize，/ 假设KeySize是已定义的常数int NumGdepthPage; / 局部深度达到全局深度的页面数赛旺踌核领过淄谍鄙南谬揉泼雌崇赶轻粟怜亏遁琅幌训语桑籽奋睛夸笋踞高级数据结构高级数据结构360JYPtemplate int hash(const Type& key, const int i); / 用均匀散列将key/转换为二进制位序列，返回与i个最低位对应/ 的整数，并作为目录项下标int buddy(const int index);/ 根据指向一个页面的目录项下/ 标index，返回指向其伙伴页面的目录项下标，这可/ 以通过对index的首个二进制位作取反操作实现template int size(const page* p); / 返回页面p中记录个数template void coalesce(const page* p, const page* buddy); / 将页面p及其伙伴buddy的记录合并到页面p，并释放页/ 面buddy晴烤醒捧必今频骏鹏暮幢氓忙浩梧菇绘显囱烂荤啄咐伯肆缝僵乔豪谚涵德高级数据结构高级数据结构361JYPtemplate Boolean PageSearch(const Type& key, const page* p);/ 在页面p中查找关键字key。找到返回TRUE，否则返回/ FALSEtemplate void enter(const record& r, const page* p); / 将新记录r/插入页面p，并执行pNumRecords+;template void PageDelete(const Type& key, const page* p); / 从/ 页面p中删除关键字为key的记录，并执行pNumRecords-;荆祁令闸冒致藩询撰糖萌殖赌婚溯嘲容辈畏甜腊急炊汞绵委梨淫材圣虐金高级数据结构高级数据结构362JYPtemplate page* find(const Type& key) / 在整个表中查找关键/ 字为key的记录。找到返回该记录所在页面的地址，/否则返回0 int index = hash(key, gdepth); page* p = rdirectoryindex.paddr; if (PageSearch(key, p) return p; else return 0; template void insert(const record& r, const Type& key) / 将新/ 记录r插入整个表中 page* p = find(key); / 检查key是否已存在 if (p) return; / key已存在 int index = hash(key, gdepth);察陀厕跨莉袄措缠诞虎御腕熄蹬七挤淹淳免筹虎握鸵压兼优泳脂豺妄拧跺高级数据结构高级数据结构363JYP Boolean StillFull = FALSE; p = rdirectoryindex.paddr; if (pNumRecords != PageSize) enter(r, p); / 页面未满，插 / 入新记录 else do rdirectoryindex.LocalDepth+; if (rdirectoryindex.LocalDepth gdepth) gdepth+; if (gdepth KeySize) 报告错误; return; 目录扩展一倍并设置新增加的目录项; NumGdepthPage = 0;/ 初始化局部深度达到全/ 局深度的页面数 分配一个新页面q; 畦能髓了彩婉凡倒贵筹西疽凝痕蜘蓟癣包按圃妓绞偏阵涛娃粤周傈点捻名高级数据结构高级数据结构364JYP int buddyindex = buddy(index); rdirectorybuddyindex.LocalDepth = rdirectoryindex.LocalDepth; rdirectorybuddyindex.paddr =q; 将页面p中的关键字重新散列到页面p和q; if (rdirectoryindex.LocalDepth = gdepth) NumGdepthPage += 2; int index = hash(key, gdepth); / 通过散列函数得到记录r/ 的目录项下标 p = rdirectoryindex.paddr;/ 得到r应存入的页面p，p / 必是原来的页面p和新分配页面q之一 if (pNumRecords != PageSize) enter(r, p); else StillFull = TRUE; while (StillFull = TRUE);邓氨繁工家趴泅峙材蕴睫拘裁匹豺毕置极宠嗽广脚休毕辨涩裕韧逞错瘸质高级数据结构高级数据结构365JYPtemplate void Delete(const Type& key) / 从整个表中删除关键字/ 为key的记录 page* p = find(key); if (p) PageDelete(key, p); int index = hash(key, gdepth); int buddyindex = buddy(index); page* bp = rdirectorybuddyindex.paddr; if (size(p)+size(bp) = PageSize) if (index 1) gdepth-; 将目录收缩为原来的一半; / 由于总是合并到小下标目/ 录项所指页面，前面一半目录项已设置好 根据剩下的目录项的局部深度重新设置NumGdepthPage;/ 此操作只访问目录而不必访问页面 void main( ) gdepth = 1; 颅厄蚁锁扬科靶揪呼幂菜宵翻季袄降欣盂返骑爱倡迹绊郎箩蜒住匠隋访晕高级数据结构高级数据结构368JYP 分析：分析：利用带目录动态散列，查询任何页面只需利用带目录动态散列，查询任何页面只需要要1次访问目录和次访问目录和1次访问页面。次访问页面。 假设页面存储在磁盘上。如果目录在初始时全部假设页面存储在磁盘上。如果目录在初始时全部进入内存，则查询任何页面只需要进入内存，则查询任何页面只需要1次磁盘访问。次磁盘访问。 带目录动态散列的性能很好，但也需要空间代价。带目录动态散列的性能很好，但也需要空间代价。 空间利用率空间利用率定义为整个表中存储的记录数与分配定义为整个表中存储的记录数与分配的总空间之比。的总空间之比。 设设L(k)表示存储表示存储k个记录所需要的平均页面数。个记录所需要的平均页面数。 L(k)与页面的容量与页面的容量p有关。当所有记录都可存入有关。当所有记录都可存入一个页面时，一个页面时，L(k) = 1。帽青孺触驾甚踞石迪迂舆拷锦箕硼奢冠莎量粪既境莹兽叛肉吕阮匣戒连耐高级数据结构高级数据结构369JYP 当当k超过页面的容量时，目录将扩展为上下两部超过页面的容量时，目录将扩展为上下两部分，上半部分有分，上半部分有j个记录，下半部分有个记录，下半部分有k j个记录。个记录。由于从由于从k个记录中选个记录中选0, 1, , k个记录的总共组合数个记录的总共组合数是是 所以上半部分有所以上半部分有j个记录（下半部分必有个记录（下半部分必有k j个记录）个记录）的概率是的概率是褒舒残天坏惶徊拦馆垄郭鄂绊景滋共怎孵丽扦徐栏帛炮咬蚂氏功嘘透翟徐高级数据结构高级数据结构370JYP因此因此Mendelson的研究结果表明的研究结果表明于是于是 空间利用率空间利用率 = ln 2 0.69砖破紫依鼻干坯佯荤鉴叭娜虱耻读庸字蝴乾攘腑喂混聂蒸制刽现黔婉恋垛高级数据结构高级数据结构371JYP 往一个满页面中插入第往一个满页面中插入第p + 1个记录将导致溢出，个记录将导致溢出，从而增加一个新页面。采用均匀散列函数，这两个从而增加一个新页面。采用均匀散列函数，这两个页面各包含约页面各包含约p/2的记录，即空间利用率为的记录，即空间利用率为50%。 随着插入和删除操作的不断进行，新近分裂的页随着插入和删除操作的不断进行，新近分裂的页面将存储更多记录。所以，空间利用率将介于面将存储更多记录。所以，空间利用率将介于50%到到100%之间。这说明了上述结论的合理性。之间。这说明了上述结论的合理性。 Fagin等人的实验研究结果表明，可扩展散列的等人的实验研究结果表明，可扩展散列的性能至少与性能至少与B树同样好或更好。在查找和插入时间树同样好或更好。在查找和插入时间方面，可扩展散列明显更好；在空间利用率方面，方面，可扩展散列明显更好；在空间利用率方面，两者几乎相同。两者几乎相同。您六鼠函蝶挑矢叼瘸撕课鲍嗅刻胯轧支涂咀功伸汉鄂岳尊苟捧激绽迭藐厦高级数据结构高级数据结构372JYP8.9.2 无目录动态散列无目录动态散列 带目录散列至少需要一次间接访问。带目录散列至少需要一次间接访问。 假设连续地址空间足够大，可容纳所有记录，则假设连续地址空间足够大，可容纳所有记录，则可以除去目录。这种方法称为可以除去目录。这种方法称为无目录散列无目录散列。 设初始时散列表中有设初始时散列表中有4个页面，页面的地址用个页面，页面的地址用2个个二进制位表示。二进制位表示。 散列函数直接给出关键字所在页面的地址。每一散列函数直接给出关键字所在页面的地址。每一个页面对应一个唯一的地址。个页面对应一个唯一的地址。 图图8.43（a）表示将关键字）表示将关键字A0, B0, C2, A1, B1和和C3加入无目录散列表后的结果。加入无目录散列表后的结果。蹭肇捻盲周韶歌睁膝梦泥娄毋郡鹿岂滨杆志驯来乎轰邪康匪技夷后鸯浪倾高级数据结构高级数据结构373JYP碴凭盼胀附步勒膝佣啥搏佩憋珐茫望烧盐堆肾讳哈刚肘酬猿辛生诡恒火妆高级数据结构高级数据结构374JYP 页面溢出时，分配一个溢出页存放新关键字，同页面溢出时，分配一个溢出页存放新关键字，同时在文件尾端增加一个新页面，并将第一个页面的时在文件尾端增加一个新页面，并将第一个页面的关键字在第一个页面和新页面之间分配。关键字在第一个页面和新页面之间分配。 如果原来的页面地址包含如果原来的页面地址包含r个二进制位，则第一个二进制位，则第一个页面和新页面的地址包含个页面和新页面的地址包含r + 1个二进制位。个二进制位。 往图往图8.43（a）中插入）中插入C5的结果如图的结果如图8.43（b）所）所示。示。 接着插入接着插入C1的结果如图的结果如图8.43（c）所示。）所示。偏署探用儒致以奈有扳凑痘蒸嚎棍缮胎莲荧株诱千炕赤缄殃呀楚峙燥闭瘁高级数据结构高级数据结构375JYP 最终，页面数将增长一倍，从而完成一个扩展阶最终，页面数将增长一倍，从而完成一个扩展阶段。新的扩展阶段便开始了。页面地址由段。新的扩展阶段便开始了。页面地址由r到到r + 1个个二进制位确定的阶段称为二进制位确定的阶段称为第第r个扩展阶段个扩展阶段。 下图反映了文件在第下图反映了文件在第r个扩展阶段的某一个时刻个扩展阶段的某一个时刻q的状态：的状态：囱身雌情诺嫌吱虞凶疤仇侨质缎翻屠瘤煮晒砌乏观脑彬暮碧呸枪沾疫龚瞧高级数据结构高级数据结构376JYP 在第在第r个扩展阶段的开始，共有个扩展阶段的开始，共有m = 2r个页面，所个页面，所有页面的地址都由有页面的地址都由r个二进制位确定。个二进制位确定。 在时刻在时刻q，增加了，增加了q个新页面。分隔线个新页面。分隔线q左边的页左边的页面已分裂。从分隔线面已分裂。从分隔线q的右边到分隔线的右边到分隔线m的页面待分的页面待分裂。分隔线裂。分隔线m右边的页面是在本阶段新增加的页面。右边的页面是在本阶段新增加的页面。这部分页面的地址由这部分页面的地址由r + 1个二进制位确定。个二进制位确定。 分隔线分隔线q也指示下一个将分裂的页面。所有小于也指示下一个将分裂的页面。所有小于q的页面的地址都由的页面的地址都由r + 1个二进制位确定。个二进制位确定。盟肠础仔蔼氦屈匀阑蚌郴详笺帐栗尸民单聋涡幌了吭墅簧蝴尺怀示颓舱但高级数据结构高级数据结构377JYP 为此需要采用下列程序实现的散列函数：为此需要采用下列程序实现的散列函数： if ( hash(key, r) q) page = hash(key, r + 1); else page = hash (key, r); 如果必要，沿着溢出指针查找;函数函数h(key, r)的值域是的值域是0, 2r 1。 无目录动态散列总需要有溢出页的支持。无目录动态散列总需要有溢出页的支持。 对于直接由散列函数确定地址的页面中的关键字，对于直接由散列函数确定地址的页面中的关键字，查询只需要一次访问。然而，对于溢出链表中的关查询只需要一次访问。然而，对于溢出链表中的关键字，查询需要的访问次数大于等于键字，查询需要的访问次数大于等于2。 在增加新页面时，需要将被分裂页面及其溢出链在增加新页面时，需要将被分裂页面及其溢出链表中的关键字重新散列到两个页面中。表中的关键字重新散列到两个页面中。廉奇羊兹判少蚜块炳谍赦表迄凯噶龄纠案左瓷马磷扁揪渣睛喇骆存孵吗覆高级数据结构高级数据结构378JYP