Структуры данных и алгоритмы (1021739), страница 25
Текст из файла (страница 25)
Двоичное дерево можно определить как АТД со структурой двоичного дереваи операторами LEFTCHILD(n), RIGHTCHILD(n), PARENT(rc) и NULL(n). Первые три оператора возвращают соответственно левого сына, правого сына иродителя узла п (если такового нет, то возвращается Л). Последний операторвозвращает значение true тогда и только тогда, когда дерево с корнем п является нулевым. Реализуйте эти операторы для двоичного дерева, представленного в табл. 3.1.3.16. Напишите процедуры для семи операторов деревьев из раздела 3.2, используяследующие реализации деревьев:а) указатели на родителей;б) список сыновей;в) указатели на самого левого сына и на правого брата.3.17.
Степенью узла называется количество его сыновей. Покажите, что в произвольном двоичном дереве количество листьев на единицу больше числа узловсо степенью 2.3.18. Докажите, что в любом двоичном дереве высотой h количество узлов не превышает 2*+1 - 1. Двоичное дерево высотой h с максимально возможным количеством узлов называется полным двоичным деревом.*3.19. Предположим, что дерево реализуется с помощью указателей на самого левогосына, на правых братьев и на родителя. Разработайте алгоритмы обхода деревьев в прямом, обратном и внутреннем порядке, не используя при этом стека, как сделано в листинге 3.3.3.20.
Пусть символы а, Ь, с, d, e и / имеют вероятности появления соответственно0.07, 0.09, 0.12, 0.22, 0.23, 0.27. Найдите оптимальный код Хаффмана и нарисуйте соответствующее ему дерево. Какова средняя длина кода?;УПРАЖНЕНИЯ101*3.21. Пусть Г — дерево Хаффмана и пусть лист, помеченный символом а, имеетбольшую глубину, чем лист, помеченный символом Ь.
Докажите, что вероятность символа Ь не меньше, чем вероятность символа а.*3.22. Докажите, что в результате выполнения алгоритма Хаффмана для заданных вероятностей получается оптимальный код. Совет: используйте упражнение 3.21.Библиографические замечанияВ работах [11] и [47] рассматриваются математические свойства деревьев. В [65] и [81]приведена дополнительная информация о деревьях двоичного поиска.
Многие работы, приведенные в главе 6 и относящиеся к графам и их применению, содержаттакже материал о деревьях.Алгоритм поиска оптимального кода, описанный в разделе 3.4, взят из работы [54].В [83] дано современное исследование этого алгоритма.102ГЛАВА 3. ДЕРЕВЬЯГЛАВА 4•"-..,.• -ОсновныеоператорымножествМножество является той базовой структурой, которая лежит в основании всей математики. При разработке алгоритмов множества используются как основа многихважных абстрактных типов данных, и многие технические приемы и методы разработаны для реализации абстрактных типов данных, основанных именно на множествах. В этой главе мы рассмотрим основные операторы, выполняемые над множествами, и опишем некоторые простые реализации множеств.
Мы представим "словарь" и"очередь с приоритетами" — два абстрактных типа данных, основанных на моделимножеств. Реализации для этих АТД приведены в этой и следующей главах.4.1. Введения в множестваМножеством называется некая совокупность элементов, каждый элемент множества или сам является множеством, или является примитивным элементом, называемым атомом. Далее будем предполагать, что все элементы любого множества различны, т.е. в любом множестве нет двух копий одного и того же элемента.Когда множества используются в качестве инструмента при разработке алгоритмов и структур данных, то атомами обычно являются целые числа, символы, строкисимволов и т.п., и все элементы одного множества, как правило, имеют одинаковыйтип данных. Мы часто будем предполагать, что атомы линейно упорядочены с помощью отношения, обычно обозначаемого символом "<" и читаемого как "меньше чем"или "предшествует".
Линейно упорядоченное множество S удовлетворяет следующимдвум условиям.1.Для любых элементов а и b из множества S может быть справедливым толькоодно из следующих утверждений: а < Ь, а = Ъ или Ъ < а.2. Для любых элементов a, b и с из множества S таких, что а < Ъ и Ъ < с, следуета < с (свойство транзитивности)1.Множества целых и действительных чисел, символов и символьных строк обладают естественным линейным порядком, для проверки которого можно использовать оператор отношения < языка Pascal. Понятие линейного порядка можно определить для объектов, состоящих из множеств упорядоченных объектов.
Формулировку такого определения мы оставляем читателю в качестве упражнения.(Прежде чем приступать к общей формулировке, рассмотрите пример двух множеств целых чисел, одно из которых состоит из чисел 1 и 4, а второе — из чисел 2и 3, и сформулируйте условия, в соответствии с которыми первое множество будетбольше или меньше второго.)1Классическое определение отношения линейного строгого порядка требует выполнениясвойств антирефлексивности, антисимметричности и транзитивности. Здесь выполнение свойства антирефлексивности обеспечивает требование различности элементов любого множества, асформулированное свойство 1 является парафразом "стандартного" определения свойства антисимметричности. — Прим.
ред.Система обозначений для множествМножество обычно изображается в виде -последовательности его элементов, заключенной в фигурные скобки, например {1, 4} обозначает множество, состоящееиз двух элементов, — чисел 1 и 4. Порядок, в котором записаны элементы множества, не существен, поэтому мы можем писать {4, 1} так же, как и {1, 4>, при записи одного и того же множества.
Отметим (и будем это иметь в виду в дальнейшем),что множество не является списком (хотя бы по признаку произвольного порядказаписи элементов), но для представления множеств мы будем использовать списки.Повторим также еще раз, что мы предполагаем отсутствие повторяющихся элементов в множестве, поэтому набор элементов {1,4, 1} не будем воспринимать как1множество .Иногда мы будем представлять множества с помощью шаблонов, т.е. выраженийвида {ж | утверждение относительно х], где "утверждение относительно х" являетсяформальным утверждением, точно описывающим условия, при выполнении которыхобъект х может быть элементом множества.
Например, шаблон {х \ х — положительное целое число и х < 1000} представляет множество {1, 2, ..., 1000}, а запись {х | для2произвольного целого у, х = у } определяет множество точных квадратов целых чисел. Отметим, что множество точных квадратов бесконечно и его нельзя представитьперечислением всех его элементов.Фундаментальным понятием теории множеств является понятие отношения принадлежности к множеству, обозначаемое символом €.
Таким образом, запись х е Аобозначает, что х принадлежит множеству А, т.е. является элементом этого множества; элемент х может быть атомом или другим множеством, но А не может быть атомом. Запись х г А означает, что "х не принадлежит множеству А", т.е. х не являетсяэлементом множества А.
Существует специальное множество, обозначаемое символом0, которое называется пустым множеством и которое не имеет элементов. Отметим,что 0 является именно множеством, а не атомом, хотя и не содержит никаких элементов. Утверждение х е 0 является ложным для любого элемента х, в то же времязапись * s у (если * и у атомы) просто не имеет смысла: здесь синтаксическая ошибка, а не ложное утверждение.Говорят, что множество А содержится в множестве В (или включается в множество В), пишется А С В или В ^А, если любой элемент множества А является такжеэлементом множества В.
В случае А с В также говорят, что множество А являетсяподмножеством множества В. Например, {1, 2} с {1, 2, 3}, но множество {1, 2, 3} неможет быть подмножеством множества {1, 2}, поскольку множество {1, 2, 3} содержит элемент 3, которого не имеет множество {1, 2}. Каждое множество включается всамого себя, пустое множество содержится в любом множестве.
Два множества равны, если каждое из них содержится в другом, т.е. они имеют одни и те же элементы.Если А Ф В и А с В, то множество А называют собственным, истинным или строгим подмножеством множества В.Основными операциями, выполняемыми над множествами, являются операцииобъединения, пересечения и разности. Объединением множеств А и В (обозначаетсяА и В) называется множество, состоящее из элементов, принадлежащих хотя бы одному из множеств А и В. Пересечением множеств А и В (обозначается А п В)называется множество, состоящее только из тех элементов, которые Принадлежат имножеству А, и множеству В. Разностью множеств А и В (обозначается А \ В) называется множество, состоящее только из тех элементов множества А, которые не принадлежат множеству В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
