Множество из пяти символов с их вероятностями, а также типичное дерево Хаффмана. Символ А возникает в 55% случаев и ему присваивается однобитовый код, что вносит вклад 0.55х1 в среднюю длину. Символ Е возникает лишь в 2% случаев. Ему присваивается код длины 4, и его вклад равен
0.02 X 4 = 0.08.

Тогда средняя длина кода равна
0.55 X 1 + 0.25 X 2 + 0.15 X 3 + 0.03 х 4 + 0.02 х 4 = 1.7 бит на символ.

Удивительно, но тот же результат получится, если сложить значения вероятностей четырех внутренних узлов кодового дерева: 0.05 4 + 0.2 + 0.45 + 1 = 1.7. Это наблюдение дает простой способ вычисления средней длины для кодов Хаффмана без использования операции умножения. Надо просто сложить значения внутренних узлов дерева.

Если сложить числа в левом столбце, то получится 1.7, а складывая числа в остальных столбцах, убеждаемся, что это число 1.7 есть сумма четырех 0.02, четырех 0.03, трех 0.15, двух 0.25 и одного 0.55. Это рассуждение годится и в общем случае. Легко видеть, что в дереве типа Хаффмана (т.е., дереве, в котором каждый узел есть сумма своих потомков) взвешенная сумма листьев, где вес листа - это его расстояние до корня, равна сумме всех внутренних узлов. (Это свойство было мне сообщено Джоном Мотилом.)

Сложение величин всех внутренних узлов дает вклад от этих двух листьев. Поскольку эти листья выбраны произвольно, ясно, что эта сумма включает в себя аналогичный вклад от всех остальных узлов, то есть, равна средней длине кода. Эта число также равно сумме левого столбца или сумме всех внутренних узлов, которая и определит среднюю длину кода. Отметим, что в доказательстве нигде не предполагалось, что дерево - двоичное. Поэтому это свойство выполнено для любого дерева, в котором узлы являются суммой своих потомков.