10 竞赛树.pdf

下载 第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给出由a～h 共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 给出有a～e 共5名选手参加的比赛，最后的赢家为c。 a) b) 图10-1 竞赛树 a) 8名选手 b) 5名选手 虽然图1 0 - 1的两棵树都是完全二叉树（实际上树 a 还是满二叉树），但在现实中竞赛问题所 对应的树不一定都是完全二叉树。然而，使用完全二叉树可以减小比赛的场次。对于 n 名选手 的比赛，比赛场次为「l o g2 nù个。因为图1 0 - 1中竞赛树的每一个内部节点都记录了对应比赛的赢 3 0 4 第二部分 数 据 结 构 下载 家，所以称之为赢者树（winner tree）。1 0 . 4节将介绍另一类型的树，称为输者树（ loser tree）， 故名思义，它的每一个内部节点记录的是比赛的输者。竞赛树在某些情况下也被称为选择树 （selection tree）。 为适应计算机的实现，需要对赢者树作一些适当的修改。不妨假定赢者树为完全二叉树。 定义 [赢者树] 对于n 名选手，赢者树是一棵含n 个外部节点，n－1个内部节点的完全二叉树， 其中每个内部节点记录了相应赛局的赢家。 为决定一场比赛的赢家，假设每个选手有一得分且赢者取决于对两选手得分的比较。在最 小赢者树（mi