|
|
|
|
采用败者树的目的是在进行最小键值的查找时减少比较次数。
|
|
|
|
败者树是一棵完全二叉树，其中每个结点的键值都取其两个子结点的键值中的较小者，因此，根结点的键值是这棵树中所有结点的键值中最小的。这就像k个参加淘汰赛的球队，胜者（值较小者）进入下一轮的比赛，根结点为冠军（值最小者）。
|
|
|
|
败者树的构造过程是：对具有k个记录的序列，首先用这k个记录作为叶结点，然后把相邻的两个结点进行比较，把键值小的记录（优胜者）作为这两个结点的父结点，按此方法自下而上一层一层地产生败者树的结点。为了节约内存空间，非叶子结点可不包含整个记录，只要存放记录的键值及指向该记录的指针即可。
|
|
|
|
败者树的根结点的值是构成败者树的元素中最小的，在后面的应用中，往往把根结点的值输出并用一个新的元素替换，要求构成新的败者树，这时只要在原来的败者树的基础上进行调整即可。调整仅在从根到新加入的叶子结点的树枝上的结点及其兄弟结点之间进行，自下而上进行比较并调整其父结点。
|
|
|
|
|
|
|
|
| |
|
|
|
