7.7.5 最佳归并树

文件经过置换-选择排序之后，得到的是长度不等的初始归并段。下面讨论如何组织初始归并段的归并顺序，使I/O访问次数最少。

m-路归并排序可用一棵m叉树描述，因为每一次作m路归并都需要m个归并段参加，因为，归并段树是一棵只有度为0和度为m的结点的严格m叉树。

设由置换-选择排序得到9个初始归并段，其长度（记录数）依次为：9，30，12，18，3，17，2，6，24。

现作3-路归并，各叶结点表示参加归并的一个初始归并段，叶结点上的权值表示初始归并过程中的记录数，根结点表示最终生成的归并段，叶结点到根结点的路径长度表示归并过程中的归并趟数，各非叶结点代表归并成的新的归并段，则归并树的带权路径长度WPL即为归并过程中的总记录数，因而在归并过程中，总的I/O次数为2*WPL=484。

归并方案不同，所得归并树亦不同，树的带权路径长度（外存I/O次数亦不同）。为了优化归并树的WPL，可以将Huffman树的思想推广到M叉树的情形。在归并树中，让记录数少的初始归并段最先归并，记录数多的初始归并段最晚归并，就可以建立总的I/O次数达到最少的最佳归并树。对上述9个初始归并段可构造成最佳归并树，按此树进行归并，仅需对外村进行446次读写，这棵树便称为最佳归并树。

Huffman树是一棵严格3叉树。若只有8个初始归并段，设上例中少了一个长度为30的归并段。如果在设计归并方案时，缺额的归并段留着最后，即除了最后一次作2-路归并外，其他各次归并仍都是3-路归并，此归并方案的外存读写次数为386。显然不是最佳方案。

正确的做法是，若初始归并段不足构成一棵严格m叉树时，需添加长度为0的“虚段”，按照Huffman树的原则，权为0的叶子应离根最远。

如何判定添加虚段的数目？

设度为0的结点有N0(=n)个，度为m的结点有Nm个，则对严格m叉树有N0=(m-1)Nm+1，由此可以得出Nm=(N0-1)/(m-1)。

如果（N0-1）%（m-1）=0(%为取余运算)，则说明这N0个叶结点（初始归并段）正好可以构造m叉归并树。此时，内结点有Nm个。

如果（N0-1）%（m-1）=u不等于0，则说明对于这N0个叶结点，其中有u个多余，不能包含在m叉归并树中。为构造包含所有N0个初始归并段的m叉归并树，应在原有Nm个内结点的基础上再增加一个内结点。它在归并树中代替了一个叶结点位置，被代替的叶结点家伙是哪个刚才多出的u个叶结点，再加上m-u-1个空归并段，就可以建立归并树。