algorithm - 具有最大高度的哈夫曼树，好问题？

Question

我在 DS 类(class)的家庭作业解决方案中遇到了一个很好的问题。以下哪项(for large n)为 Huffman Tree 创建最高高度。以下选项中每个序列的元素显示字符在输入文本中的频率，而不显示字符。

1) sequence of n equal numbers

2) sequence of n consecutive Fibonacci numbers.

3) sequence <1,2,3,...,n>

4) sequence <1^2,2^2,3^2,...,n^2> 

Anyone could say, why this solution select (2)? thanks to anyone.

Answer 1

让我们在这里分析各种选项。

N 个相等数字的序列意味着将使用底部叶节点的实际符号创建平衡树。

序列 1-N 具有以下属性:当您开始对两个最低元素进行分组时，它们的总和将迅速上升到其他元素之上，这是一个示例:

如您所见，4+5 和 7+8 中的组本身并没有对树的高度做出贡献。

将两个 3 节点分组为 6 后，节点 4 和 5 排在下一个，这意味着形成的每个新组都不会影响其高度。大多数人会，但不是全部，这是重要的事实。

使用正方形的序列(注意:正方形如问题中的第三个序列，1^2, 2^2, 3^2, 4^2, ..., N^2 ，而不是方形图元素)与 1-N 序列的行为有些相同，有时会使用不同于刚刚形成的元素的其他元素，这会降低高度:

正如您在这里看到的，36+49 也发生了同样的情况，它对树的高度没有贡献。

但是，斐波那契数列不同。当您将两个最低节点分组时，它们的总和最多会覆盖下一个项目，但不会超过其中一个，这意味着正在形成的每个新组也将在下一个中使用，因此 每个新组formed 将有助于树的高度。这与其他 3 个示例不同。