11.5 最佳归并树

01

最佳归并树

1、假设由置换-选择得到9个初始归并段，其长度（即记录数）依次为：9,30,12,18,3,17,2,6,24。现作3-路平衡归并，其归并树（表示归并过程的图）如下图所示，

图中每个圆圈表示一个初始归并段，圆圈中数字表示归并段的长度。假设每个记录占一个物理块，则两趟归并所需对外存进行的读/写次数为：（9+30+12+18+3+17+2+6+24）*2*2=484。若将初始归并段的长度看成是归并树中叶子结点的权，则此三叉树的带权路径长度的两倍恰好为484。显然，归并方案不同，所得归并树亦不同，树的带权路径长度也不同。

2、若对长度不等的m个初始归并段，构造一棵赫夫曼树作为归并树，便可使在进行外部归并时所需对外存进行的读/写次数达最少。