赫夫曼树的频率I‘’th字母表是2^i？

Question

我‌为DS考试做准备。我‌看了我的笔记。其中一个问题是不完善的。有人能帮我描述一下吗？

假设在文本中，I‘’th英语字母的频率是2^i (^表示幂)。这些人物的赫夫曼树有多高？

我‌需要人帮我.‌

Answer 1

高度是n - 1，其中n是字母表的大小(让我们称之为h(n))。

证明：

1. 基本情况。n = 2，高度是1。
2. 步骤：2 ^ n > 2 ^ 0 + ... + 2 ^ (n - 1)。因此，大小为n的字母表的树看起来是这样的:根有两个子树:带有n-th字符(最常见的一个)的叶子和大小为n - 1的字母表的树根。这意味着它的高度是h(n) = h(n - 1) + 1 = (n - 2) + 1 = n - 1。

我假设高度是通往一片叶子的最长路径中的边数。如果我们将高度定义为多个顶点，则答案是n。