(2)败者树 在利用选择树进行归并时,将两个子女结点中的败者(关键码值较大者)上 升到父结点,同时另加进一个结点以代表比赛的全局获胜者的索引值,称这种选 择树为败者树。 败者树比赛过程:将新进入树的结点与其父结点进行比赛把败者存放在父结 点中而把胜者再与上一级的父结点进行比赛这样的比赛不断进行,直到根结点 处。并将全局获胜者的索引值存放在添加结点中。 在授课过程中的难点是,如何借助完全二叉树完成赢者树和败者树的构造。 3)最佳归并 最佳归并树:如果在进行多路归并的时候,各初始顺串的长度不同,对外存 扫描的次数,即执行时间会产生影响。把所有初始顺串的块数作为树的叶结点的 权值,如果是K路归并则建立起一棵K-叉 Huffman树。这样的一棵 Huffman树 就是最佳归并树。通过最佳归并树进行多路归并可以使对外存的ⅣO降到最少 提高归并执行效率。 授课过程中,举例讲解最佳归并树的构造方法和构造过程。 6课后练习和实习 课后练习重点是置换排序、二路归并排序以及最佳归并树的构造。 可以安排2道综合上机实习题。安排1次习题讲评 7总结 外部排序是内部排序的延伸和扩展,是实际数据管理系统中广泛应用的基本 操作。学完本章后,关键是要能够在实践中理解课程核心内容和技术难点。 参考文献: []张铭,王腾蛟,赵海燕,《数据结构与算法》,高等教育出版社,2008年6月。—普 通高等教育“十一五”国家级规划教材。 [2]张铭、赵海燕、王腾蛟、宋国杰、高军,北京大学“数据结构与算法”教学设计,《计 算机教育》2008第20期。获得“英特尔杯2008年全国计算机教育优秀论文评比”一等 奖 3]北京大学《数据结枃与算法》精品课程网站(2008年北京市“精品课程”暨国家“精品 Ee"),http://www.jpk.pkueducn/pkujpk/course/sjjg/（2）败者树 在利用选择树进行归并时，将两个子女结点中的败者（关键码值较大者）上 升到父结点，同时另加进一个结点以代表比赛的全局获胜者的索引值，称这种选 择树为败者树。 败者树比赛过程：将新进入树的结点与其父结点进行比赛把败者存放在父结 点中而把胜者再与上一级的父结点进行比赛这样的比赛不断进行，直到根结点 处。并将全局获胜者的索引值存放在添加结点中。 在授课过程中的难点是，如何借助完全二叉树完成赢者树和败者树的构造。 3) 最佳归并 最佳归并树：如果在进行多路归并的时候，各初始顺串的长度不同，对外存 扫描的次数，即执行时间会产生影响。把所有初始顺串的块数作为树的叶结点的 权值，如果是 K 路归并则建立起一棵 K-叉 Huffman 树。这样的一棵 Huffman 树 就是最佳归并树。通过最佳归并树进行多路归并可以使对外存的 I/O 降到最少， 提高归并执行效率。 授课过程中，举例讲解最佳归并树的构造方法和构造过程。 6 课后练习和实习 课后练习重点是置换排序、二路归并排序以及最佳归并树的构造。 可以安排 2 道综合上机实习题。安排 1 次习题讲评。 7 总结 外部排序是内部排序的延伸和扩展，是实际数据管理系统中广泛应用的基本 操作。学完本章后，关键是要能够在实践中理解课程核心内容和技术难点。 参考文献： [1] 张铭，王腾蛟，赵海燕，《数据结构与算法》，高等教育出版社，2008 年 6 月。——普 通高等教育“十一五”国家级规划教材。 [2] 张铭、赵海燕、王腾蛟、宋国杰 、高军，北京大学“数据结构与算法”教学设计，《计 算机教育》2008 第 20 期。获得“英特尔杯 2008 年全国计算机教育优秀论文评比”一等 奖。 [3] 北京大学《数据结构与算法》精品课程网站（2008 年北京市“精品课程”暨国家“精品 课程”）， http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/