8.7.5 最佳归并树

教材导航 · 第8章

原书定位

印刷页P390起,对应PDF第402页。下文为目视整理的知识提要;完整内容见原书对照。

初始段长度不等时,以各段长度为叶权,构造 kk 叉哈夫曼树:反复合并最短的 kk 个段,让较长段少参与归并,使 WPL 最小。

rr 个初始段要满足 (r−1) mod (k−1)=0(r-1)\bmod(k-1)=0,否则补零权虚段:

z=((k−1)−((r−1) mod (k−1))) mod (k−1)z=\big((k-1)-((r-1)\bmod(k-1))\big)\bmod(k-1)

补足后内部合并结点数为 (r+z−1)/(k−1)(r+z-1)/(k-1)。虚段不产生实际数据读写,应与真实段一起按最小权原则处理,不能把缺的归并路数随意留到最后一轮。

若权以记录数计,WPL=∑wiliWPL=\sum w_i l_i 为归并处理的记录总量,读写记录量为 2WPL2WPL;若题求块 I/O,还需按块容量和各次取整计算。该式通常不含最初生成归并段的读写。

普通三路归并树

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

三叉哈夫曼最佳归并树

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

补零权虚段后的最佳归并树

补零权虚段后的最佳归并树,原书P391。

对应练习

8.7 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P390,PDF第402页

原书对照,原书P391,PDF第403页

原书对照,原书P392,PDF第404页