胜者树与败者树

2020-05-01 本文已影响0人小幸运Q

胜者树：

是树形选择排序的一种变形，本身是一棵完全二叉树。

胜者树：在树形选择排序一节中，对于无序表{49，38，65，97，76，13，27，49}创建的完全二叉树如下图所示，构建此树的目的是选出无序表中的最小值。

胜者树.png

败者树：

而败者树恰好相反，其双亲结点存储的是左右孩子比较之后的失败者，而胜利者则继续同其它的胜者去比较。

所示为一棵 5-路归并的败者树，其中 b0—b4 为树的叶子结点，分别为 5 个归并段（已经预先排好了序）中存储的记录的关键字。

败者树

注：为了防止在归并过程中某个归并段变为空，处理的办法为：可以在每个归并段最后附加一个关键字为最大值的记录。这样当某一时刻选出的冠军为最大值时，表明 5 个归并段已全部归并完成。（因为只要还有记录，最终的胜者就不可能是附加的最大值）
存储：

败者树是完全二叉树，因此数据结构可以采用一维数组。其元素个数为k个叶子结点、k-1个比较结点、1个冠军结点共2k个。ls[0]为冠军结点，ls[1]--ls[k- 1]为比较结点，b[0]--b[k-1]为叶子结点。另外b[k]为一个附加的辅助空间，不属于败者树，初始化时存着MINKEY的值。

待排数据：

image.png

由败者树得知，其最终胜者为 29，设为 MINIMAX 值，将其输出到初始归并文件中，同时再读入下一个记录 14（所有等待中的段头元素中的最小值），调整败者树：

image.png

当进行关键字的比较时，先比较序号，序号小的为胜者；序号相同的关键字值小的为胜者。（序号一开始都初始化为0，相当于段号）

通过不断地向败者树中读入记录，会产生多个 MINIMAX，直到最终所有叶子结点中的序号都为 2，此时产生的新的 MINIMAX 值的序号 2，表明此归并段生成完成，而此新的 MINIMAX 值就是下一个归并段中的第一个记录。