骤直至到达胜者结点，即P==0时败者树重构完毕。
败者树的创建方法：
在败者树中添加一个编号为K的辅助叶子结点，该结点中的记录值为待排序记录不可能达到的最小值MI，令所有分支结点的初值均为K（每插入一条记录就会有一个分支结点的值由K变为0～K-1之间的值）。依次从K个初始归并段中读取第一条记录插入败者树中，这样经过K次插入后，各分支结点的初始值K将被0～K-1所替代，此时即创建好了一棵败者树。
第10章 算法设计策略及应用实例
1. 具有什么特征的问题适合用分治策略求解？
三个特征：
（1） （2）
原问题可以分解成规模较小、相互独立和类型相同的子问题；
子问题的规模缩小到一定的程度，就不需要再分解，可以容易地求解；
（3） 所有子问题的解能够合并成原问题的解。 2. 递归算法和迭代算法的区别是什么？
递归算法是利用函数直接或者间接调用自身来完成某个计算过程。为了求解规模为n的问题，设法将它分解成规模较小的问题，并能从规模较小的解构造出原问题的解。迭代法根据问题规模为i-1的解，由问题的迭代性质，构造问题规模为i的解，最后得到规模为n的原问题的解。所以，递归算法是从大到小、从上到下地构造问题的解，而迭代算法是从小到大、从下到上地构造或者逼近问题的解。 3. 具有什么性质的问题适合贪心策略求解？
具有如下性质：第一、最优子结构性质；第二、贪心选择性质。 4. 具有什么性质的问题适合动态规划策略求解？
具有如下性质：第一、最优子结构性质；第二、子问题重叠性质。
5. 贪心策略和动态规划策略之间的差别有哪些？
两种策略的不同之处在于，贪心策略做出的每步贪心选择都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一步的最优解无需保留。动态规划策略的全局最优解一定包括某个局部最优解，但是不一定包括前一个局部最优解，因此动态规划策略需要保存之前的所有局部最优解。
6. 回溯策略和分支限界策略之间的差别有哪些？
回溯策略和分支限界策略的差别体现在以下方面：第一、分支限界策略没有限制树的搜索方法，可以是广度优先搜索，也可以是最小成本搜索，而回溯策略采用的是深度优先搜索；第二、分支限界策略只能用于优化问题，而回溯策略可以用于非优化问题，例如求问题的可行解。