В чём заключается принцип построения дерева Хаффмана?

Принцип построения дерева Хаффмана заключается в следующем: ru.wikipedia.org intuit.ru

1. Символы входного алфавита образуют список свободных узлов. ru.wikipedia.org Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в сжимаемое сообщение. ru.wikipedia.org
2. Выбираются два свободных узла дерева с наименьшими весами. ru.wikipedia.org
3. Создаётся их родитель с весом, равным их суммарному весу. ru.wikipedia.org
4. Родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка. ru.wikipedia.org
5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0. ru.wikipedia.org
6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. ru.wikipedia.org Он и будет считаться корнем дерева. ru.wikipedia.org

Идея алгоритма состоит в том, что, зная вероятности появления символов в сообщении, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. ru.wikipedia.org Символам с большей вероятностью ставятся в соответствие более короткие коды. ru.wikipedia.org