8.7.5 最佳归并树
原书定位
印刷页P390起,对应PDF第402页。下文为目视整理的知识提要;完整内容见原书对照。
初始段长度不等时,以各段长度为叶权,构造 叉哈夫曼树:反复合并最短的 个段,让较长段少参与归并,使 WPL 最小。
个初始段要满足 ,否则补零权虚段:
补足后内部合并结点数为 。虚段不产生实际数据读写,应与真实段一起按最小权原则处理,不能把缺的归并路数随意留到最后一轮。
若权以记录数计, 为归并处理的记录总量,读写记录量为 ;若题求块 I/O,还需按块容量和各次取整计算。该式通常不含最初生成归并段的读写。

普通三路归并树,原书P391。

三叉哈夫曼最佳归并树,原书P391。

补零权虚段后的最佳归并树,原书P391。
对应练习
关联知识
原书对照
展开原书对照截图


