SICP по-русски

Заметим, что для заданных частот символов справедливо утверждение о том, что сумма двух наименьших частот меньше любой из оставшихся частот. Следовательно, дерево будет вырождено. Также отметим, что:

1+2 = 3 = 4 - 1,

3+4 = 7 = 8 - 1,

…

2ⁿ-1 + 2ⁿ = 2ⁿ⁺¹-1.

Таким образом дерево Хаффмана для n=5 будет выглядеть следующим образом (слева частоты обозначены простыми числами, а справа через степени двойки для наглядности):

Для n=10 дерево будет таким (вновь слева частоты обозначены простыми числами, а справа через степени двойки):

Самый часто встречающийся символ имеет частоту 2^n-1 и находится сразу налево от корня, то есть кодируется одним битом 0.

Самый редко встречающийся символ имеет частоту 1=2⁰ и находится на самом длинном пути в дереве, состоящем из n-1 единицы, то есть имеет код 11…1 (число битов в коде равно n-1).