yandex rtb 1
ГоловнаЗворотній зв'язок
yande share

Алгоритмы структуры данных

3.4. Двоичные деревья

Деревья, которые мы определили в разделе 3.1, называются упорядоченными ориентированными деревьями, поскольку сыновья любого узла упорядочены слева направо, а пути по дереву ориентированы от начального узла пути к его потомкам. Двоичное (или бинарное) дерево — совершенно другой вид. Двоичное дерево может быть или пустым деревом, или деревом, у которого любой узел или не имеет сыновей, или имеет либо левого сына, либо правого сына, либо обоих. Тот факт, что каждый сын любого узла определен как левый или как правый сын, существенно отличает двоичное дерево от упорядоченного ориентированного дерева.

Пример 3.9. Если мы примем соглашение, что на схемах двоичных деревьев левый сын всегда соединяется с родителем линией, направленной влево и вниз от родителя, а правый сын — линией, направленной вправо и вниз, тогда на рис. 3.12,а, б представлены два различных дерева, хотя они оба похожи на обычное (упорядоченное ориентированное) дерево, показанное на рис. 3.13. Пусть вас не смущает тот факт, что деревья на рис. 3.12,а, б различны и не эквивалентны дереву на рис. 3.13. Дело в том, что двоичные деревья нельзя непосредственно сопоставить обычному дереву. Например, на рис. 3.12,а узел 2 является левым сыном узла 1 и узел 1 не имеет правого сына, тогда как на рис. 3.12,6 узел 1 не имеет левого сына, а имеет правого (узел 2). В тоже время в обоих двоичных деревьях узел 3 является левым сыном узла 2, а узел 4 — правым сыном того же узла 2.

Обход двоичных деревьев в прямом и обратном порядке в точности соответствует таким же обходам обычных деревьев. При симметричном обходе двоичного дерева с корнем п левым поддеревом t1 и правым поддеревом T2 сначала проходится поддерево Т1, затем корень п и далее поддерево T2. Например, симметричный обход дерева на рис. 3.12,а даст последовательность узлов 3, 5, 2, 4, 1.

Представление двоичных деревьев

если именами узлов двоичного дерева являются их номера 1, 2, ..., п, то подходящей структурой для представления этого дерева может служить массив cellspace записей с полями leftchild (левый сын) и rightchild (правый сын), объявленный следующим образом:

var

cellspaсе:   array[1..maxnodes]   of record

leftchild:   integer;

rightchild:   integer

end;

В этом представлении cellspace[i].leftchild является левым сыном узла і, а cellspace[i].rightchild Іправым сыном. Значение 0 в обоих полях указывает на то, что узел і не имеет сыновей.

Пример 3.10. Двоичное дерево на рис. 3.12,а можно представить в виде табл. 3.1.

Таблица 3.1. Представление двоичного дерева

 

Значение поля leftchild

Значение поля rightchild

1

2 3 4 5

2

3

0

0

0

0

4

5

0

0

Пример: коды Хаффмана

Приведем пример применения двоичных деревьев в качестве структур данных. Для этого рассмотрим задачу конструирования кодов Хаффмана. Предположим, мы имеем сообщения, состоящие из последовательности символов. В каждом сообщении символы независимы и появляются с известной вероятностью, не зависящей от позиции в сообщении. Например, мы имеем сообщения, состоящие из пяти символов а, b, с, d, е, которые появляются в сообщениях с вероятностями 0.12, 0.4, 0.15, 0.08 и 0.25 соответственно. Мы хотим закодировать каждый символ последовательностью из нулей и единиц так, чтобы код любого символа являлся префиксом кода сообщения, состоящего из последующих символов. Это префиксное свойство позволяет декодировать строку из нулей и единиц последовательным удалением префиксов (т.е. кодов символов) из этой строки.

Пример 3.11. В табл. 3.2 показаны две возможные кодировки для наших пяти символов. Ясно, что первый код обладает префиксным свойством, поскольку любая последовательность из трех битов будет префиксом для другой последовательности из трех битов; другими словами, любая префиксная последовательность однозначно идентифицируется символом. Алгоритм декодирования для этого кода очень прост: надо поочередно брать по три бита и преобразовать каждую группу битов в соответствующие символы. Например, последовательность 001010011 соответствует исходному сообщению bed.

Таблица 3.2. Два двоичных кода

Символ

Вероятность

Код1

Код 2

а

b

с

d

е

0.12

0.40

0.15

0.08

0.25

000

001

010

011

100

000

11

01

001

10

Легко проверить, что второй код также обладает префиксным свойством. Процесс декодирования здесь не отличается от аналогичного процесса для первого кода. Единственная сложность для второго кода заключается в том, что нельзя сразу всю последовательность битов разбить на отдельные сегменты, соответствующие символам, так как символы могут кодироваться и двумя и тремя битами. Для примера рассмотрим двоичную последовательность 1101001, которая опять представляет символы bed. Первые два бита 11 однозначно соответствуют символу Ь, поэтому их можно удалить, тогда получится 01001. Здесь 01 также однозначно определяет символ с й т.д.

Задача конструирования кодов Хаффмана заключается в следующем: имея множество символов и значения вероятностей их появления в сообщениях, построить такой код с префиксным свойством, чтобы средняя длина кода (в вероятностном смысле) последовательности символов была минимальной. Мы хотим минимизировать среднюю длину кода для того, чтобы уменьшить длину вероятного сообщения (т.е. чтобы сжать сообщение). Чем короче среднее значение длины кода символов, тем короче закодированное сообщение. В частности, первый код из примера 3.11 имеет среднюю длину кода 3. Это число получается в результате умножения длины кода каждого символа на вероятность появления этого символа. Второй код имеет среднюю длину 2.2, поскольку символы а и d имеют суммарную вероятность появления 0.20 и длина их кода составляет три бита, тогда как другие символы имеют код длиной 2.

Можно ли придумать код, который был бы лучше второго кода? Ответ положительный: существует код с префиксным свойством, средняя длина которого равна 2.15. Это наилучший возможный код с теми же вероятностями появления символов. Способ нахождения оптимального префиксного кода называется алгоритмом Хаффмана. В этом алгоритме находятся два символа а и Ь с наименьшими вероятностями появления и заменяются одним фиктивным символом, например ж, который имеет вероятность появления, равную сумме вероятностей появления символов а и Ь. Затем, используя эту процедуру рекурсивно, находим оптимальный префиксный код для меньшего множества символов (где символы а и b заменены одним символом х). Код для исходного множества символов получается из кодов замещающих символов путем добавления 0 и 1 перед кодом замещающего символа, и эти два новых кода принимаются как коды заменяемых символов. Например, код символа а будет соответствовать коду символа х с добавленным нулем перед этим кодом, а для кода символа b перед кодом символа х будет добавлена единица.

Можно рассматривать префиксные коды как пути на двоичном дереве: прохождение от узла к его левому сыну соответствует 0 в коде, а к правому сыну — 1. Если мы пометим листья дерева кодируемыми символами, то получим представление префиксного кода в виде двоичного дерева. Префиксное свойство гарантирует, что нет символов, которые были бы метками внутренних узлов дерева (не листьев), и наоборот, помечая кодируемыми символами только листья дерева, мы обеспечиваем префиксное свойство кода этих символов.

Пример 3.12. Двоичные деревья для кодов 1 и 2 из табл. 3.2 показаны на рис. 3.14 (дерево слева соответствует коду 1, а дерево справа — коду 2).

Для реализации алгоритма Хаффмана мы используем лес, т.е. совокупность деревьев, чьи листья будут помечены символами, для которых разрабатывается кодировка, а корни помечены суммой вероятностей всех символов, соответствующих листьям дерева. Мы будем называть эти суммарные вероятности весом дерева. Вначале каждому символу соответствует дерево, состоящее из одного узла, в конце работы алгоритма мы получим одно дерево, все листья которого будут помечены кодируемыми символами. В этом дереве путь от корня к любому листу представляет код для символа-метки этого листа, составленный по схеме, согласно которой левый сын узла соответствует 0, а правый — 1 (как на рис. 3.14).

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

Пример 3.13. Последовательные шаги выполнения алгоритма Хаффмана для кодируемых символов и их вероятностей, заданных в табл. 3.2, представлены на рис. 3.15. Здесь видно (рис.  3.15,д), что символы а, b, с, d и е получили соответственно коды 1111, 0, 110, 1110 и 10. В этом примере существует только одно нетривиальное дерево, соответствующее оптимальному коду, но в общем случае их может быть несколько. Например, если бы символы b и е имели вероятности соответственно 0.33 и 0.32, то после шага алгоритма, показанного на рис. 3.15,в, можно было бы комбинировать b и е, а не присоединять е к большому дереву, как это сделано на рис. 3.15,г.

Теперь опишем необходимые структуры данных. Во-первых, для представления двоичных деревьев мы будем использовать массив TREE (Дерево), состоящий из записей следующего типа:

record

leftchild:   integer;

rightchild:   integer;

parent:   integer

end

Указатели в поле parent (родитель) облегчают поиск путей от листа к корню при записи кода символов. Во-вторых, мы используем массив ALPHABET (Алфавит), также состоящий из записей, которые имеют следующий тип:

record

symbol:   char;

probability:   real;

leaf:   integer  {  курсор  }

end

В этом массиве каждому символу (поле symbol), подлежащему кодированию, ставится в соответствие вероятность его появления (поле probability) и лист, меткой которого он является (поле leaf). В-третьих, для представления непосредственно деревьев необходим массив FOREST (Лес). Этот массив будет состоять из записей с полями weight (вес) и root (корень) следующего типа:

record

weight:   real;

root:   integer

end

Начальные значения всех трех массивов, соответствующих данным на рис. 3.15,а, показаны на рис. 3.16. Эскиз программы (псевдопрограмма, т.е. программа на псевдоязыке, как описано в главе 1) построения дерева Хаффмана представлен в листинге 3.8.

 

Листинг 3.8. Программа построения дерева Хаффмана

(1)   while существует более одного дерева в лесу do

 begin

(2)          i:= индекс  дерева  в  FOREST с наименьшим весом;

(3)                     j:= индекс дерева в  FOREST со вторым наименьшим весом;

(4)                      Создание  нового узла  с левым сыном FOREST[i].root и правым сыном FOREST[j].root;

(5)                      Замена в  FOREST дерева  і деревом,   чьим корнем является новый узел и чей вес равен

FOREST[i].weight +  FOREST[j].weight;

(6)                     Удаление дерева j из массива FOREST

end;

 

Для реализации строки (4) листинга 3.8, где увеличивается количество используемых ячеек массива TREE, и строк (5) и (6), где уменьшается количество ячеек массива FOREST, мы будем использовать курсоры lasttree (последнее дерево) и lastnode (последний узел), указывающие соответственно на массив FOREST и массив TREE. Предполагается, что эти курсоры располагаются в первых ячейках соответствующих массивов1. Мы также предполагаем, что все массивы имеют определенную объявленную длину, но здесь мы не будем проводить сравнение этих ограничивающих значений со значениями курсоров,

В листинге 3.9 приведены коды двух полезных процедур. Первая из них, lightones, выполняет реализацию строк (2) и (3) листинга 3.8 по выбору индексов двух деревьев с наименьшими весами. Вторая процедура, функция сгеа1е(n1, n2), создает новый узел и делает заданные узлы п1 и п2 левым и правым сыновьями этого узла.

 

 

40