Дерево Хаффмана с максимальной высотой, хорошие вопросы?

Question

Я столкнулся с хорошим вопросом в одном решении домашней работы в курсе DS. , которые из следующих (for large n) создают наибольшую высоту для Huffman Tree. элементы каждой последовательности в следующем варианте показывают the frequencies of character in input text и не показаны символы.

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> 

Любой желающий мог сказать, почему это решение выбрать (2)? спасибо всем.

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, это не способствовало высоте дерева.

Однако, последовательность fibonacci отличается. Когда вы группируете два наименьших узла, их сумма будет в лучшем случае свертывать следующий элемент, но не более одного из них, что означает, что каждая новая сформированная группа будет использоваться и в следующем, так что каждая новая группа будет сформирована способствуют росту дерева. Это отличается от других 3 примеров.