5.8 选择树

  • 一个已排序的序列称为一个 「归并段 run」
  • 「选择树 selection tree」 是一棵二叉树,其中每一个结点都代表该结点两个儿子中的较小者。这样,树的根结点表示树中最小元素的结点。

假设有 kk 个归并段,要将其合并成一个单独的排序序列。每一个序列都由若干个记录组成,并且按指定的域 key(称为关键字)升序排列。令 nnkk 个归并段的记录总数。

最直接的方法是进行 k1k-1 次比较,从而确定下一个要输出的记录。对于 k>2k>2,可以采用选择树的思想来减少寻找下一个最小元素所需要的比较次数。

如图表示 k=8k=8 情况下的选择树。选择树的建立过程可以比作进行比赛的过程。获胜者是有较小关键值的记录。于是,树中的每一个非叶子结点表示比赛的获胜者,而根结点表示最后的获胜者,即最小的关键字。这里一个叶子结点表示相应归并段中的第一条记录。由于要合并的记录通常很大,所以每一个结点只包含一个指向其所代表的记录的指针。因此,根结点包含一个指向归并段 4 的第一条记录的指针。

5-26

此时,归并段 4 的下一个记录进入选择树。这个记录值为 15。现在需要重建这棵树,那么只需要沿着结点 11 到根结点的路径重复以上的竞赛,即结点 10 和结点 11 比赛得到结点 5(15 < 20),结点 4 和结点 5 比赛得到结点 2(9 < 15),结点 2 和结点 3 比赛得到根结点(8 < 9)。如图。

5-27

竞赛在兄弟结点之间进行,结果放在父结点中。每次比较结束后,下一次比较都发生在树的更高一层。树的层数是 log2k+1\lceil \log_2k \rceil + 1。因此 重建树的时间开销是 O(log2k)O(\log_2k)。每当一个记录合并到输出文件,树都需要重建。因此,合并所有 nn 个记录所需的时间是 O(nlog2k)O(n\log_2k)。第一次构建选择树所需要的时间是 O(k)O(k)。因此,合并所有 nn 个归并段总时间是 O(nlog2k)O(n\log_2k)

  • 「败者树 tree of loser」 在每个非叶子结点中存放一个失败结点(而不是获胜者)的关键字值的竞争树。败者树可以简化树的重建过程,每次重建树时比赛无需发生在兄弟结点之间,只需与其父结点比较,然后再将败者存放于父结点,将胜者再与父结点的父结点比较。增加一个附加的结点 ---- 结点 0,用来表示比赛最终的获胜者。如图。

5-28

results matching ""

    No results matching ""