(71)王道数据结构-败者树

基本概念

败者树是胜者树的一种变体。在败者树中，用父结点记录其左右子结点进行比赛的败者，而让胜者参加下一轮的比赛。败者树的根结点记录的是败者，需要加一个结点来记录整个比赛的胜利者。采用败者树可以简化重构的过程。

败者树是计算机科学学科里的一种数据结构，可用于外部排序中提高效率。 [1] 败者树实际上是一棵完全二叉树，可以看做是胜者树的一种变体。败者树简化了重构。败者树的重构只是与该结点的父结点的记录有关，而胜者树的重构还与该结点的兄弟结点有关。败者树中每个叶节点存放各归并段在归并过程中当前参加比较的记录，每个非叶结点记忆其两个子女结点中记录排序码小的结点（即败者）。

重要性质

1.败者树解决问题:使用多路平衡归并可减少归并趟数，但从k个归并段选出一个最小/最大元素需要对比关键字k-1次，构造败者树可以使关键字对比次数减少到[log2k]
2.败者树可视为一棵完全二叉树(多了一个头)。k个叶节点分别对应k个归并段中当前参加比较的元素，非叶子节点用来记忆左右子树中的“失败者”，而胜者往上继续进行比较，一直到根节点