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. Тот, кто хочет отведать плод, должен влезть на дерево.
|