Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 115
Текст из файла (страница 115)
В дереве с минимальным весом на максимальном уровне листья присутствуют в парах, т.е. везде, где есть левый сын, имеется и правый сын и наоборот. ДОКАЗАТЕЛЬСТВО. Существует только конечное число бинарных деревьев с и листьями. Для каждого из них подсчитаем 644 ГЛАВА 15. Деревья ДОКАЗАТЕЛЬСТВО. Допустим, что на максимальном уровне имеется единственный сын; пусть это будет левый сын, помеченный символом в. Правого сына нет, поэтому имеем дерево, изображенное на рис. 15.35. Если мы теперь удалим левого сына и обозначим родителя меткой в, то в результате получим дерево с меньшим весом, а это противоречит предположению о том, что дерево имеет минимальный вес.
Рис. 15.35 ЛЕММА 15.18. В дереве с минимальным весом два символа с минимальными частотами расположены на максимальном уровне. ДОКАЗАТЕЛЬСТВО. Если теорема не верна, то имеется символ а на уровне 1, с частотй 7; и символ Ь на уровне 1 с частотой Уз, где 1, > 1, и 7", > Д. В общий вес дерева эти два символа вносят величину 1,7; +1 7,. Если эти символы поменять местами, то их вклад в общий вес дерева составит 1,7; +1 7о Но 1,7, + 1,~1 — (1,Д + Я,) = 1,7, + 1.~) — 1,71 — Яг = = (1* -1.Н.)' — Л) > >О, поскольку 1, — 1, > О и 7", — 11 > О. Таким образом, 1гу, ч 1,7' > 1 7; +1 7„поэтому перестановка символов приводит к уменьшению веса дерева, что противоречит предположению о том, что дерево имеет минимальный вес. Теперь все готово для формулировки основной теоремы.
ТЕОРЕМА 15.20. Для заданного множества символов с соответствующими ча- стотами дерево Хаффмана является деревом с минимальным весом, ДОКАЗАТЕЛЬСТВО. Докажем теорему, используя индукцию по числу символов. Для двух символов, скажем, а и Ь, дерево Хаффмана изображено на рис. !5.36 и действительно является деревом с минимальным весом. Таким образом, теорема верна для п = 2. Предположим, что утверждение теоремы справедливо для дерева с и Л, символами. Пусть Т„.ь, — дерево минимального веса, содер- А жашее и + 1 символ. Предположим, что а и Ь с частотами )', и 7ь ЯвлЯютсЯ символами с самыми низкими частотами.
Тогда по лемме 15.18 они могут быть братьями на самом высоком уровне 1+1. Теперь удалим а и Ь из дерева и присвоим их родителю символ с с частотой 7„+ 7ь. Назовем это дерево Т„. Поскольку в де- реве только п символов, то по индуктивному предположению сушествует дерево ЛЕММА 15.19.
Существует дерево с минимальным весом, в котором два символа с наименьшими частотами имеют одного родителя. ДОКАЗАТЕЛЬСТВО. По лемме!5.17 каждый лист на максимальном уровне имеет брата. По лемме 15.18 оба символа с минимальным весом, к примеру, а и Ь, находятся на одном уровне. Если они не братья, то поскольку находятся на одном уровне, замена а на Ь не повлияет на вес дерева. РАЗДЕЛ 15.3. Взвешенные деревья 645 Хаффмана с минимальным весом с этими символами.
Назовем дерево Т„'. Поскольку Т„' имеет минимальный вес, то вес Т„' меньше или равен весу дерева Т„. Теперь заменим с с частотой г" + гь на родителя с сыновьями а и Ь, образуя дерево Т„'+,. Другими словам, для перехода от дерева Т„.ь1 к дереву Т„используется обратный процесс. Но это совпадает с построением дерева Хаффмана с и+1 символом, поскольку для построения дерева Хаффмана с и+ 1 символом следовало бы начать с а и Ь и образовать дерево с родителем, имеющим частоту у;+ ~в, так что если рассматривать с как представителя этого дерева, то построение дерева Хаффмана Т„' является продолжением дерева Хаффмана Т'~,.
Теперь имеются четыре дерева; деревья Хаффмана Т„' и Т„'ч,, где Т„' — дерево с минимальным весом, и деревья Т„и Т„ч, где Т„.ь, — дерево с минимальным весом. Мы перешли от дерева Т„' к дереву Т„'+, и от дерева Т„к дереву Т„+,, заменяя с с частотой г" + гь на вершины а и Ь с частотами г', и Гь и их родителя. Теперь рассмотрим, каким образом это влияет на вес дерева. При переходе от дерева Т„к дереву Т ~, вершина с с частотой 1 + гь, длиной 1, общим весом 1(Х* + Хь) заменяется вершиной а с частотой г"„длиной 1+ 1 и вершиной Ь с частотой Гь, длиной 1+ 1, общий вес которых равен У+1)+~ь(1+1) =Ц~.+1ь)+);+~в. Таким образом, увеличение веса дерева составило г" + гь.
Аналогично при переходе от дерева Т„' к дереву Т„'~, увеличение веса дерева также равно г" + гь. Поскольку вес дерева Т„' меньше или равен весу дерева Т„и увеличение веса при переходе от дерева Т„'ч, и Т„.ь1 одно и то же, то вес дерева Т„'~, меньше или равен весу Т„ч.м Таким образом, дерево Т„'ч, — дерево минимального веса. ° ° УПРАЖНЕНИЯ 1. Заданы следующие символы и их коды: а) закодируйте слово п1зсизз; б) закодируйте слово зиеев; в) декодируйте слово 101011111100110101101; г) декодируйте слово 11001001000101101010010. 646 ГЛАВА тб. Деревья 2. Заданы следующие символы и их коды: а) закодируйте слово тпаВгетатгса; б) закодируйте слово гпатглаЬ; в) декодируйте слово 11100101111000111001; г) декодируйте слово 100101110110010100111001.
3. Заданы следующие символы с их частотами и три множества кодов. Найдите вес каждого кода и выберите наиболее подходящий для компактного хранения данных. 4. Заданы следующие символы с их частотами и три множества кодов. Найдите вес каждого кода и выберите наиболее подходящий для компактного хранения данных. РКЗДЕЛ тдз. Взвешенные деревья 647 б. Заданы следующие символы с их частотами: а) постройте дерево Хаффмана; б) определите код Хаффмана; в) найдите вес кода; г) закодируйте слово сгаЬ; д) закодируйте слово Ьаг; е) декодируйте 1100111; ж) декодируйте 10011110. 6. Заданы следующие символы с их частотами; а) постройте дерево Хаффмана; б) определите код Хаффмана; в) найдите вес кода; г) закодируйте слово Ьгеая; д) закодируйте слово ЬагЬег; е) декодируйте 11011011000; ж) декодируйте 11110110111101101.
7. Заданы следующие символы с их частотами: а) постройте дерево Хаффмана; б) определите код Хаффмана; в) найдите вес кода; г) закодируйте слово егазег; д) закодируйте слово г1агяег. е) декодируйте 10010110001100; ж) декодируйте 0011011001111001. 8. Заданы следующие символы с их частотами: а) постройте дерево Хаффмана; б) определите код Хаффмана; в) найдите вес кода; г) закодируйте слово дйоз1; д) закодируйте слово сйоозе; е) декодируйте 100010010000111101; ж) декодируйте 10001001110111101; з) декодируйте 11100010000100110001. б4В ГЛАВА 15. Деревья 9.
Заданы следующие символы с их частотами: а) постройте дерево Хаффмана; б) определите код Хаффмана; в) найдите вес кода. 10. Заданы следующие символы с их частотами: а) постройте дерево Хаффмана; б) определите код Хаффмана. в) найдите вес кода; г) закодируйте слова тпооп1гуЫапдтозез; д) закодируйте слово Гооз1еяз. 11.
Заданы следующие символы с их частотами: а) постройте дерево Хаффмана; б) определите код Хаффмана; РЯЗДЕЛ 15.4. Обход бинарных деревьев 649 в) найдите вес кода; г) закодируйте слова еая1о7ГИеяипапйвеяГо7ГИегпооп; д) закодируйте слово ягеаГег. 12. Заданы следуюшие символы с их частотами: а) постройте дерево Хаффмана; б) определите код Хаффмана; в) найдите вес кода; г) закодируйте слова еаяГо7Яеяипапг1гиея1о7!Иетооп; д) закодируйте слова 1ГдИГяоий 13. Докажите теорему 15.14: В любом бинарном дереве путевые коды для ли- стьев дерева являются префиксным кодом.
15.4. ОБХОД БИНАРНЫХ ДЕРЕВЬЕВ В данном разделе рассматриваются три способа обхода бинарного дерева, при которых каждая вершина посещается в точности один раз. Внимание будет сосредоточено на деревьях, изображаюших арифметичесткие выражения, хотя такие обходы имеют также другое использование.
Сначала представим арифметические выражения с помощью деревьев, а затем рассмотрим способы их обхода. Деревья, изображающие арифметические выражения, обладают тем свойством, что все их внутренние вершины являются бинарными операторами. Рассмотрим выражение А+В. Соответствуюшее ему дерево изображено на рис. !5.37. А+В С+Р Рис. (5.33 Рис. 15.37 Воспользуемся нисходящим принципом обработки, который продемонстрируем на примере.
Рассмотрим выражение (А+ В) х (С+ П). Оно представляет собой произведение А+ В и С+ Р, поэтому сначала формируем дерево, изображенное на рис. 15.38. Далее, поскольку выражение А+  — это сумма А и В, а С+ Р— сумма С и Р, то мы формируем дерево, изображенное на рис. 15.39. 660 ГЛАВА 75. Деревья /' Е, Рис. /5.40 Рис. 15.39 Каждое арифметическое выражение, содержащее бинарный оператор, по сути является бинарной операцией над двумя арифметическими выражениями (которые могут и не содержать арифметические операции).
Начинаем с корня и, если выражение в вершине имеет вид Е1 о Ез, где о — бинарная операция над выражениями Е„и Ез, заменяем вершину деревом, изображенным на рис. 15.40. Повторяем тот же процесс для вершин Е, и Ез. Продолжаем действовать таким образом, пока не останется вершин, содержащих бинарные операции. Теперь покажем три способа обхода дерева, которое задает арифметическое выражение. В каждом случае используем команду обработать (и), где и — узел.
Оставим этот термин пока неопределенным, поскольку его значение будет зависеть от того, чего мы хотим достичь при прохождении вершин. Для наших целей достаточно рассмотреть обычную команду печати символа. Начнем с обхода дерева в центрированном порядке. При таком обходе мы обращаем процесс, использованный при создании дерева. Если задано дерево, изображенное на рис. 15.40, где о — бинарная операция над выражениями Е1 и Ез, обрабатываем (или печатаем) это как Е, о Ез. В результате получается выражение в инфиксной записи, как описано в разделе 5.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
