Структуры данных и алгоритмы (1021739), страница 23
Текст из файла (страница 23)
Если мы примем соглашение, что на схемах двоичных деревьев левый сын всегда соединяется с родителем линией, направленной влево и вниз от родителя, а правый сын — линией, направленной вправо и вниз, тогда на рис. 3.12,а, бпредставлены два различных дерева, хотя они оба похожи на обычное(упорядоченное ориентированное) дерево, показанное на рис. 3.13. Пусть вас не смущает тот факт, что деревья на рис. 3.12,а, б различны и не эквивалентны дереву нарис. 3.13.
Дело в том, что двоичные деревья нельзя непосредственно сопоставитьобычному дереву. Например, на рис. 3.12,а узел 2 является левым сыном узла 1 иузел 1 не имеет правого сына, тогда как на рис. 3.12,6 узел 1 не имеет левого сына, аимеет правого (узел 2). В тоже время в обоих двоичных деревьях узел 3 является левым сыном узла 2, а узел 4 — правым сыном того же узла 2. ПОбход двоичных деревьев в прямом и обратном порядке в точности соответствуеттаким же обходам обычных деревьев. При симметричном обходе двоичного дерева с3.4. ДВОИЧНЫЕ ДЕРЕВЬЯ91корнем п левым поддеревом Tj и правым поддеревом Т2 сначала проходится поддерево TI, затем корень п и далее поддерево Т2. Например, симметричный обход деревана рис.
3.12,а даст последовательность узлов 3, 5, 2, 4, 1./\12f N*/ \43абРис. 3.12. Два двоичных дерева5Pwc. 3.13. "Обычное" деревоПредставление двоичных деревьевЕСЛИ именами узлов двоичного дерева являются их номера 1, 2, ..., и, то подходящей структурой для представления этого дерева может служить массив cellspaceзаписей с полями leftchild (левый сын) и rightchild (правый сын), объявленный следующим образом:varcellspace: array[1..maxnodes] of recordleftchild: integer;rightchild: integerend;В этом представлении cellspace[i].leftchild яв'ляется левым сыном узла i, acellspace[i\.rightchlld I— правым сыном. Значение 0 в обоих полях указывает на то,что узел z не имеет сыновей.Пример 3.10.
Двоичное дерево на рис. 3.12,а можно представить в виде табл. 3.1. ПТаблица 3.1. Представление двоичного дерева12345Значение поля leftchild23000Значение поля rightchild04500Пример: коды ХаффманаПриведем пример применения двоичных деревьев в качестве структур данных.Для этого рассмотрим задачу конструирования кодов Хаффмана. Предположим, мыимеем сообщения, состоящие из последовательности символов. В каждом сообщениисимволы независимы и появляются с известной вероятностью, не зависящей от позиции в сообщении. Например, мы имеем сообщения, состоящие из пяти символов а,Ь, с, d, e, которые появляются в сообщениях с вероятностями 0.12, 0.4, 0.15, 0.08 и0.25 соответственно.92ГЛАВА 3. ДЕРЕВЬЯМы хотим закодировать каждый символ последовательностью из нулей и едиництак, чтобы код любого символа являлся префиксом кода сообщения, состоящего изпоследующих символов.
Это префиксное свойство позволяет декодировать строку изнулей и единиц последовательным удалением префиксов (т.е. кодов символов) изэтой строки.Пример 3.11. В табл. 3.2 показаны две возможные кодировки для наших пятисимволов. Ясно, что первый код обладает префиксным свойством, поскольку любаяпоследовательность из трех битов будет префиксом для другой последовательности изтрех битов; другими словами, любая префиксная последовательность однозначноидентифицируется символом. Алгоритм декодирования для этого кода очень прост:надо поочередно брать по три бита и преобразовать каждую группу битов в соответствующие символы.
Например, последовательность 001010011 соответствует исход-,ному сообщению bed.Таблица 3.2. Два двоичных кодаСимволВероятностьКод 1Код 2а0.120.400.150.080.25000001010011100000110100110ЬсdеЛегко проверить, что второй код также обладает префиксным свойством. Процессдекодирования здесь не отличается от аналогичного процесса для первого кода. Единственная сложность для второго кода заключается в том, что нельзя сразу всю последовательность битов разбить на отдельные сегменты, соответствующие символам, так каксимволы могут кодироваться и двумя и тремя битами.
Для примера рассмотрим двоичную последовательность 1101001, которая опять представляет символы bed. Первыедва бита 11 однозначно соответствуют символу Ь, поэтому их можно удалить, тогда получится 01001. Здесь 01 также однозначно определяет символ с и т.д. ПЗадача конструирования кодов Хаффмана заключается в следующем: имея множество символов и значения вероятностей их появления в сообщениях, построитьтакой код с префиксным свойством, чтобы средняя длина кода (в вероятностномсмысле) последовательности символов была минимальной.
Мы хотим минимизировать среднюю длину кода для того, чтобы уменьшить длину вероятного сообщения(т.е. чтобы сжать сообщение). Чем короче среднее значение длины кода символов,тем короче закодированное сообщение. В частности, первый код из примера 3.11имеет среднюю длину кода 3. Это число получается в результате умножения длиныкода каждого символа на вероятность появления этого символа.
Второй код имеетсреднюю длину 2.2, поскольку символы а та. d имеют суммарную вероятность появления 0.20 и длина их кода составляет три бита, тогда как другие символы имеют коддлиной 21.Можно ли придумать код, который был бы лучше второго кода? Ответ положительный: существует код с префиксным свойством, средняя длина которого равна 2.15. Этонаилучший возможный код с теми же вероятностями появления символов.
Способнахождения оптимального префиксного кода называется алгоритмом Хаффмана. Вэтом алгоритме находятся два символа а и Ь с наименьшими вероятностями появления и заменяются одним фиктивным символом, например х, который имеет вероятность появления, равную сумме вероятностей появления символов а и Ъ. Затем, используя эту процедуру рекурсивно, находим оптимальный префиксный код для1Отсюда следует очевидный вывод, что символы с большими вероятностями появлениядолжны иметь самые короткие коды. — Прим. ред.3.4. ДВОИЧНЫЕ ДЕРЕВЬЯ93меньшего множества символов (где символы а и Ь заменены одним символом х).
Коддля исходного множества символов получается из кодов замещающих символов путем добавления О и 1 перед кодом замещающего символа, и эти два новых кода принимаются как коды заменяемых символов. Например, код символа а будет соответствовать коду символа х с добавленным нулем перед этим кодом, а для кода символаЪ перед кодом символа х будет добавлена единица.Можно рассматривать префиксные коды как пути на двоичном дереве: прохождение от узла к его левому сыну соответствует 0 в коде, а к правому сыну — 1.
Еслимы пометим листья дерева кодируемыми символами, то получим представление префиксного кода в виде двоичного дерева. Префиксное свойство гарантирует, что нетсимволов, которые были бы метками внутренних узлов дерева (не листьев), и наоборот, помечая кодируемыми символами только листья дерева, мы обеспечиваем префиксное свойство кода этих символов.Пример 3.12. Двоичные деревья для кодов 1 и 2 из табл. 3.2 показаны на рис. 3.14(дерево слева соответствует коду 1, а дерево справа — коду 2).
ПabсdeadРис. 3.14. Двоичные деревья, представляющие коды с префиксным свойствомДля реализации алгоритма Хаффмана мы используем лес, т.е. совокупность деревьев, чьи листья будут помечены символами, для которых разрабатывается кодировка, а корни помечены суммой вероятностей всех символов, соответствующих листьям дерева. Мы будем называть эти суммарные вероятности весом дерева. Вначалекаждому символу соответствует дерево, состоящее из одного узла, в конце работы алгоритма мы получим одно дерево, все листья которого будут помечены кодируемымисимволами. В этом дереве путь от корня к любому листу представляет код для символа-метки этого листа, составленный по схеме, согласно которой левый сын узла соответствует 0, а правый — 1 (как на рис.
3.14).Важным этапом в работе алгоритма является выбор из леса двух деревьев с наименьшими весами. Эти два дерева комбинируются в одно с весом, равным сумме весов составляющих деревьев. При слиянии деревьев создается новый узел, которыйстановится корнем объединенного дерева и который имеет в качестве левого и правого сыновей корни старых деревьев. Этот процесс продолжается до тех пор, пока неполучится только одно дерево. Это дерево соответствует коду, который при заданныхвероятностях имеет минимально возможную среднюю длину.Пример 3.13. Последовательные шаги выполнения алгоритма Хаффмана для кодируемых символов и их вероятностей, заданных в табл. 3.2, представлены нарис. 3.15.
Здесь видно (рис. 3.15,д), что символы а, Ь, с, d и е получили соответственно коды 1111, О, 110, 1110 и 10. В этом примере существует только одно нетривиальное дерево, соответствующее оптимальному коду, но в общем случае их можетбыть несколько. Например, если бы символы Ь и е имели вероятности соответственно0.33 и 0.32, то после шага алгоритма, показанного на рис. 3.15,в, можно было быкомбинировать Ь и е, а не присоединять е к большому дереву, как это сделано нарис.
3.15,г. D94ГЛАВА 3. ДЕРЕВЬЯ0.120.40 0.15 0.08 0.25•a•b*o•d0.200.40 0.15 0.25Л•edаа. Исходная ситуацияbсеб. Слияние а с d0.600.350.400.40 0.251.00daг. Слияние а, с, d с е'daд. Законченное деревоРис. 3.15. Этапы создания дерева ХаффманаТеперь опишем необходимые структуры данных. Во-первых, для представлениядвоичных деревьев мы будем использовать массив TREE (Дерево), состоящий из записей следующего типа:recordleftchild: integer;rightchild: integer;pa ren t: integerendУказатели в поле parent (родитель) облегчают поиск путей от листа к корню при записи кода символов.
Во-вторых, мы используем массив ALPHABET (Алфавит), также состоящий из записей, которые имеют следующий тип:recordsymbol: char;probability: real;leaf: integer { курсор }endВ этом массиве каждому символу (поле symbol), подлежащему кодированию, ставится в соответствие вероятность его появления (поле probability) и лист, меткой которого он является (поле leaf). В-третьих, для представления непосредственно деревьевнеобходим массив FOREST (Лес).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
