归并树的性质

image.png
image.png
image.png
树的带权路径长度：
查看哈夫曼树中树的带权路径长度的相关概念
哈夫曼树(最优二叉树)
image.png
要让磁盘的I/O次数最少，就是WPL最小——-哈夫曼树

构造最佳归并树

二路归并

就是构造一个哈夫曼树

image.png
image.png

多路归并

之前学习的方法（3路归并），不是最佳的归并
image.png
多路归并与构造哈夫曼树类似。
image.png
image.png
对于归并段不能刚好构造一个n叉哈夫曼树时，执行归并时得到的归并树并不是最佳归并树
image.png
image.png
需要补充归并段为长度0（null）的归并段，这样的归并段叫做”虚段“。
image.png
image.png
image.png
需要补充几个虚段？
image.png

总结

image.png