1.5.2. Модификация дерева

Основная идея заключается в проверке дерева при появлении каждого нового входного символа. Если дерево не является деревом Хаффмана, его следует подправить. Рис. 1.15 дает представление о том, как это делается. Дерево на рис. 1.15а содержит пять символов А, В, С, D и Е. Для всех символов указаны их текущие частоты (в круглых скобках). Свойство Хаффмана означает, что при изучении дерева по всем уровням слева направо и снизу вверх (от листьев к корню) частоты будут упорядочены по возрастанию (неубыванию). Таким образом, нижний левый узел (А) имеет наименьшую частоту, а верхний правый (корень) имеет наибольшую частоту. Это свойство принято называть свойством соперничества.

Рис. 1.15. Обновление дерева Хаффмана.

Причина этого свойства заключается в том, что символы с большими частотами должны иметь более короткие коды и, следовательно, находиться на дереве на более высоком уровне. Требование для частот быть упорядоченными на одном уровне устанавливается для определенности. В принципе, без него можно обойтись, но оно упрощает процесс построения дерева.

Приведем последовательность операций при модификации дерева. Цикл начинается в текущем узле (соответствующем новому входному символу). Этот узел будет листом, который мы обозначим , а его частота пусть будет . На каждой следующей итерации цикла требуется сделать три действия:

1. Сравнить  с его ближайшими соседями на дереве (справа и сверху). Если непосредственный сосед имеет частоту  или выше, то узлы остаются упорядоченными и ничего делать не надо. В противном случае, некоторый сосед имеет такую же или меньшую частоту, чем . В этом случае следует поменять местами  и последний узел в этой группе (за исключением того, что  не надо менять с его родителем);

2. Увеличить частоту  с  до . Увеличить на единицу частоту всех его родителей;

3. Если  является корнем, то цикл останавливается; в противном случае он повторяется для узла, являющегося родителем .

На рис. 1.15b показано дерево после увеличения частоты узла А с 1 до 2. Легко проследить, как описанные выше три действия влияют на увеличение частоты всех предков А. Места узлов не меняются в этом простом случае, так как частота узла А не превысила частоту его ближайшего соседа справа В.

На рис. 1.15с показано, что произойдет при следующем увеличении частоты А с 2 до 3. Три узла, следующие за А, а именно, В, С и D, имели частоту 2, поэтому А переставлен с D. После чего частоты всех предков А увеличены на 1, и каждый сравнен со своими соседями, но больше на дереве никого переставлять не надо.

Рис. 1.15d изображает дерево после увеличения частоты А до 4. Поскольку узел А является текущим, его частота (равная пока еще 3) сравнивается с частотой соседа сверху (4), и дерево не меняется. Частота А увеличивается на единицу вместе с частотами всех потомков.

На рис. 1.15е узел А опять является текущим. Его частота (4) равна частоте соседа сверху, поэтому их следует поменять местами.

Это сделано на рис. l.15f, где частота А уже равна 5. Следующий шаг проверяет родителя А с частотой 10. Его следует переставить с его соседом справа Е, у которого частота 9. В итоге получается конечное дерево, изображенное на рис. 1.15g.

Тот, кто хочет отведать плод, должен влезть на дерево.
- Томас Фуллер