Длина двоичного кодирования в алгоритме Хаффмана?

Question

Какова длина самой длинной двоичной кодировки, которая возникает при использовании алгоритма Хаксмана с весами 10, 10, 10, 10, 15, 15, 50?

Есть ли быстрый способ сделать это или я должен построить дерево, а затем вычислить среднее число бит, которые я думаю был бы:

= общая длина/количество битого

Этого это дерево я сгенерировал:

Answer 1

длина самого длинного двоичного кодирования, которая возникает при использовании алгоритма Хаффмана равна высоте дерева, которое в этом случае равна 4. Таким образом, длина самой длинной woul d будет 4.

Это можно легко увидеть, что при назначении 0 в левую ветвь и от 1 до правой ветви (вы также можете это сделать наоборот), коды будут:

50: 0 

10: 1000 

10: 1001 

10: 1010 

10: 1011 

15: 110 

15: 111