内蒙古大学《算法与数据结构》讲义10竞赛树

下载第1 0章竞赛树本章将介绍一类新的树，称为竞赛树。象 9 . 3节的堆一样，竞赛树也是完全二叉树，它可用8 . 4节定义的公式化描述的二叉树来进行最有效地存储。竞赛树支持的基本操作是替换最大（或最小）元素。如果有n 个元素，操作的开销为( l o gn)。虽然利用堆和左高树也能获得同样的复杂性O ( l o gn)，但它们都不能实现可预见的断接操作。所以当需要按指定的方式断开连接时，可选择竞赛树这种数据结构。比如选择最先插入的元素，或选择左端元素（假定所有元素按从左到右的次序排列） 。本章将研究两种竞赛树：赢者树和输者树。尽管赢者树更直观、更接近现实，但输者树的实现更高效。本章的应用部分将考察另一种 N P-复杂问题箱子装载。我们将利用竞赛树来高效地实现解决箱子装载问题的两个近似算法。试一试能否用本书迄今为止所介绍的其他任意一种数据结构以相同的时间复杂性来实现这两个算法，从中你会得到一些有益的启示。10.1 引言假定在一次乒乓球比赛中有 n 名选手，该比赛采用的是突然死亡（ s u d d e n - d e a t h）的比赛规则，即一名选手只要输一场球，就被淘汰，最终必然只剩下一个赢者。定义此“幸存”的选手为竞赛赢家。图1 0 - 1给出由ah 共8名选手参加的某次比赛。图中用一棵二叉树来描述整个比赛，每个外部节点分别代表一名选手，每个内部节点分别代表一场比赛，参加每场比赛的选手是子节点所对应的两名选手。这里，同一层节点所构成的一轮比赛可以同时进行。在第一轮比赛中a 与b、c 与d、e 与f、g 与h 交战。每场比赛的赢者记录在代表该场比赛的内部节点中。在图10-1a 的例子中，第一轮比赛的4个赢家为b、d、e 和h, 因而a、c、f、g 被淘汰。下一轮比赛在b 与d，e 与h 之间进行，胜者为b 和e ，故由b、e 参加最后的决赛，最终赢者为e。图1 0 -1b 给出有ae 共5名选手参加的比赛，最后的赢家为c。图10-1 竞赛树a) 8名选手b) 5名选手虽然图1 0 - 1的两棵树都是完全二叉树（实际上树a 还是满二叉树） ，但在现实中竞赛问题所对应的树不一定都是完全二叉树。然而，使用完全二叉树可以减小比赛的场次。对于 n 名选手的比赛，比赛场次为 l o g2 n个。因为图1 0 - 1中竞赛树的每一个内部节点都记录了对应比赛的赢a)b)家，所以称之为赢者树（winner tree） 。1 0 . 4节将介绍另一类型的树，称为输者树（loser tree） ，故名思义，它的每一个内部节点记录的是比赛的输者。竞赛树在某些情况下也被称为选择树（selection tree） 。为适应计算机的实现，需要对赢者树作一些适当的修改。不妨假定赢者树为完全二叉树。定义赢者树 对于n 名选手，赢者树是一棵含n 个外部节点，n1个内部节点的完全二叉树，其中每个内部节点记录了相应赛局的赢家。为决定一场比赛的赢家，假设每个选手有一得分且赢者取决于对两选手得分的比较。在最小赢者树（min winner tree）中，得分小的选手获胜；同理，在最大赢者树（max winner tree）中，得分大的选手获胜。有时，也可用左孩子对应的选手代表赢家节点。图 10-2a 给出含8名选手的最小赢者树，而图10-2b 给出含5名选手的最大赢者树。每个外部节点之下的数字表示选手得分。图10-2 赢者树a) 最小赢者树b) 最大赢者树赢者树的一个优点在于即使一名选手得分改变了，也可以较容易地修改此树。如当选手 d的值由9改为1时，只需沿从d 到根那条路径修改二叉树，而不必改变其他比赛的结果。有时甚至还可以避免重赛某些场次。如在图10-2a 中当b 值由6改为5时，其父节点的比赛结果中b仍为输家，故此时所有比赛的结果未变，因此不必重赛b 的祖父及曾祖父节点所对应的比赛。对于一棵有n 名选手的赢者树，当一个选手的得分发生变化时，需要修改的比赛场次介于0l o g2 n 之间，因此重构赢者树需耗时O ( l o gn)。此外，由于n 名选手的赢者树在内部节点中共需进行n - 1场比赛（按从最低层到根的次序进行） ，因此赢者树的初始化时间为(n)。也可以采用前序遍历方式来完成初始化，方法是在每一访问步中安排一场比赛。例10-1 排序 可用一个最小赢者树在(nl o gn)时间内对n 个元素进行排序。首先，用n 个元素代表n 名选手对赢者树进行初始化。利用元素的值来决定每场比赛的结果，最后的赢家为具有最小值的元素，然后将该选手（元素）的值改为最大值 (如)，使它赢不了其他任何选手。在此基础上，重构该赢者树，所得到的最终赢家为该排序序列中的下一个元素。以此类推，可以完成n 个元素的排序，时耗为(n)。每次改变竞赛赢家的值并重构赢者树的时耗为( l o gn)，这个过程共需执行n- 1次，因此整个排序过程所需要的时间为(nl o gn)。例10-2 run 的产生 本书前几章所讨论的排序方法（插入排序、堆排序等）都属内部排序法（internal sorting method） ，待排序的各个元素必须放入计算机内存中。当待排序元素所需的空3 0 4第二部分数 据 结 构下载a)b)间超出内存的最大容量时，内部排序法就需要与存储了部分或所有元素的外部存储介质（如磁盘）打交道，致使排序效率不高。在这种情况下必须采用外部排序法（external sorting method） 。外部排序一般包括两步：1) 产生部分排序结果r u n；2) 将这些r u n合并在一起得到最终的r u n。假设要为含16 000个元素的记录排序，且在内部排序中一次可排序 1 0 0 0个记录。为此在第1）步中，重复以下步骤1 6次，可得到1 6个排序结果( r u n )：输入1 0 0 0个记录用内部排序法对这1 0 0 0个记录进行排序输出排序结果r u n接下来需产生最终的排序结果，即完成上述第 2) 步。在本步中要重复地将k 个run 合并成一个r u n。如在本例中有1 6个r u n（如图1 0 - 3所示） ，它们的编号分别为R1 , R2 , R16 。首先，将R1 ,R4合并得到S1，其长度为4 0 0 0个记录，然后将R5R8合并，以此类推。接下来将 S1S4合并得到T1，T1便是外部排序的最终结果。图10-3 16个r u n的四路合并一种合并k 个r u n的简单方法是：从k 个r u n的前面不断地移出值最小的元素，该元素被移至输出r u n中。当所有的元素从k 个输入r u n移至输出r u n中时，便完成了合并过程。注意到在选择输出r u n的下一元素时，只需要知道内存中每个输入 r u n的前面元素的值。故只要有足够内存保存k 个元素值，就可合并任意长度的k 个r u n。在实际应用上，我们感兴趣的是能一次输入/出更多元素以减少输入/出的次数。在上面所列举的16 000个记录的例子中，每个 r u n有1 0 0 0个记录，而内存容量亦为 1 0 0 0个记录。为合并前四个 r u n，可将内存分为五个缓冲区，每个容量为 2 0 0个记录。其中前四个为输入run 的缓冲区，第五个为输出 run 的缓冲区，用于存放合并的记录。从四个输入 r u n中各取2 0 0个记录放入输入缓冲区中，这些记录被不断地合并并放入输出缓冲区中，直到以下条件发生：1) 输出缓冲区已满。2) 某一输入缓冲区空。当第一个条件发生时，将输出缓冲区内容写入磁盘，写完之后继续进行合并。当第二个条件发生时，则从对应于空缓冲区的输入 r u n中继续读取记录放入该缓冲区，读取过程结束后合并继续进行。当这些r u n中的4 0 0 0个记录都写入输出r u n中时，四个r u n的合并过程结束（更详细的描述参见E.Horowitz, S.Sahni, D.Mehta. Fundamentals of Data Stru c t u re in C+. ComputerScience Press, 1995。 ）r u n合并所需时间的决定因素之一是第 1）步所产生的r u n的个数。通过使用赢者树，可减少r u n的个数。开始时，用一个含p 名选手的赢者树，其中每个选手对应输入集合中的一个元素。每个选手有一个值（即对应的元素值）和一个 run 号。前p 个元素的r u n号均为1。当两选手进行比赛时，具有较小run 号的选手获胜。在run 号相同的情况下，按选手的值进行比较，具有第1 0章竞赛树3 0 5下载较小值的元素成为赢家。为产生 r u n，重复地将最终赢者W 移入它的r u n号所对应的r u n中，再用下一个输入元素N取代W 原来的位置。如果N的值大于等于W的值，则将元素N 作为相同r u n的成员输出（它的r u n号与W 的相同） 。如果N的值小于W 的值，若将N 放入与W 相同的r u n中将会破坏r u n中元素的排序，因此将N的r u n号设置为W 的r u n号加1。当采用上述方法生成r u n时，r u n的平均长度约为2p。当2p 大于内存容量时，我们希望能得到更少的r u n（与上述方法相比） 。事实上，倘若输入集合已排好序 (或几乎排好序)，只需产生最后的r u n，则可直接跳到r u n的合并步，即第2）步。例10-3 k 路合并 在k 路合并(见例1 0 - 2 )中，k 个r u n要合并成一个排好序的 r u n。按例1 0 - 2中所述的方法，进行 k 路合并时，因在每一次循环中都需要找到最小值，故将每一个元素合并到输出r u n中需O (k) 时间，因此产生大小为 n 的r u n所需要的时间为O (k n)。若使用赢者树，则可将这个时间缩短为(k+nl o gk)。首先用(k) 的时间初始化含k 个选手的赢者树。这 k 个选手都是k 个被合并r u n中的头一个元素。然后将赢者移入输出 r u n中并用相应的输入 r u n中的下一个元素替代之。如果在该输入 r u n中无下一元素，则需用一个 k e y值很大(不妨为) 的元素替代之。k 次移入和替代赢家共需耗时( l o gk)。因此采用赢者树进行 k 路合并的总时间为(k+nl o gk)。练习1. 1) 描述如何用最小堆来替代最小赢者树产生 r u n（见例1 0 - 2） ，产生r u n中每一元素的时间为多少？2) 在此应用中，最小赢者树与堆相比，有哪些优点和缺点？2. 1) 在进行k 路合并时（见例1 0 - 3） ，如何用最小堆替代最小赢者树？2) 在此应用中，最小赢者树与堆相比有哪些优点和缺点？10.2 抽象数据类型Wi n n e r Tr e e在定义抽象数据类型 Wi n n e r Tree 时，假设选手数是固定的，也就是说，初始化选手数为n 的树之后，不再增减选手数。选手本身不是赢者树的组成部分，故组成赢者树的成分是图1 0 - 1所示的内部节点。因此，赢者树需要支持的操作有：创建空的赢者树、用n 名选手初始化赢者树、返回赢者、在从选手 i 到根的路径上重新进行比赛。各操作的定义在 A D T 1 0 - 1中给出。ADT10-1 赢者树的抽象数据类型描述抽象数据类型Wi n n e r Tre e实例完全二叉树，每个节点代表相应比赛的赢者，外部节点代表选手操作C re a t e( )：创建一个空的赢者树I n i t i a l i z e(a, n)：对有n 个选手a 1 :n 的赢者树进行初始化Wi n n e r( )：返回比赛的赢者R e p l a y(i)：选手i 变化时，重组赢者树3 0 6第二部分数 据 结 构下载10.3 类Wi n n e r Tr e e10.3.1 定义假设用完全二叉树的公式化描述方法来定义赢者树。 n名选手的赢者树需n-1个内部节点t 1 : n-1 。选手（或外部节点）用数组e 1 : n 表示。故t i 为数组e的一个索引而且类型为i n t。t i 给出了赢者树中节点i 对应比赛的赢者。图1 0 - 4给出