AOP_Tom1 (1021736), страница 100
Текст из файла (страница 100)
17, в котором приводится другая важная процедура, подобная алгоритму Г). Таким'образом, деревья и леса могут иметь несколько различных представлений последователыюго типа. Существует также несколько представлений связанных типов, которые описываются ниже. Первая идея связана г преобразованием представления (3) н представление (6): удалим поля 1МгО нз каждого неконцевого узла и преобразуем эту информацию в новый концевой узел предыдущего узла.
Например, деревья (2) и результате такого преобразования примут вид (НО) При этом предполагается (без потери общности), что все поля 1МгО в древовидной структуре находятся в концевых узлах. Следовательно, в естественном представлении бинарного дерева из раздела 2.3.2 поля 11.1МК и 1МгО являются взаимно исключающими и могут совместно использовать одно и то же поле в каждом узле. Узел может включать такие поля: Здесь 1.ТАС указывает, является лн второе поле связью. (Сравните это представление, например, с форматом па основе двух слов (10) из раздела 2.3.2.) Сокращая длину поля 1Мг О с 6 до 3 байт, получим, что каждый узел можно разместить в одном слоне.
Обратите, однако, внимание на то, что вместо 10 узлов мы теперь используем 15 узлов. Для леса (10) потребуется 15 слов памяти, тогда как для (2) — 20, однако в последнем случае поля 1МгО занимают 60 байт по сравнению с 30 байт в первокк случае. Таким образом, при использовании представления (10) нельзя получить никакой экономии памяти, если не применяется дополнительное пространство в полях 1МгО. Дело в том, что удаление полей 13.1МК в (10) компенсируется добавлением почти такого жс каличества новых полей Н1.1МК в добавленных узлах. Более подробно различия между этими представлениями описываются в упр.
4. В представлении дерева как стандартного бинарного дерева для поля 1.1.1МК точнее было бы использовать название 1СН11.0, поскольку оно направлено от узла- родителя к крайнему слева узлу-ребенку. Этот узел-ребенок обычно является "самым младшим' ребенком дерева, так как легче всего вставить узел слева от семьи, чем справа. Поэтому сокращение 1.СН1Ы может трактоваться, как "последний ребенок" или "крайний ребенок". Во многих приложениях древовидных структур довольно часто требуется обрап»аться к узлам дерева как по направлению вверх, так и по направлению вниз.
Прошитое дерево предоставляет возможность перехода к верхним узлам, хотя и с небольшой скоростью. Однако иногда лучше иметь в каждом узле третью связь РАНЕМТ. При ее наличии получим трижды связанное дерево (Гг»р!у йпйед лгее), каждый узел которого имеет связи 1СН1Ы, Е11ИК и РАНЕЫТ. На рис. 26 показано, представление трижды связанного дерева для (2), а пример его использования приводится в разделе 2.4. Рис. 26. Трижды связанное дерево Ясно, что связи РАНЕМТ самой по себе достаточно для полного описания структуры любого ориентированного дерева (или леса), поскольку схему любого дерева можно нарисовать, зная все нш»равленные вверх связи.
Каждый узел, за исключением корня, имеет только одного родителя, но может иметь сразу несколько детей. Поэтому для их определения проще использовать связи, направленные вверх, а не вниз. Почему же тогда они до сих пор не рассматривались? Ответ, конечно же, заключается в том, что направленные вверх связи не всегда пригодны для используемого приложения, так как порой очень трудно быстро определить, является ли узел концевым, или найти какого-либо ребенка узла. Однако есть очень важное приложение, для работы с которым достаточно иметь только связи, направленные вверх.
Рассмотрим вкратце элегантный алгоритм обработки отношений эквивалентности, предложенный М. Дж. Фишером (М. 3. Г»зс)»ег) и Б. А. Галлером (В. А. ОаНег). Отношением зквиваяе»»тности (еуи»»»а1епсе ге»айоп) ': — ' называется отношение между элементами множества о', которое удовлетворяет следующим условиял» для любых (необязательно различных) объектов х, у и з множества 5. ») Если х = у и у: — з, то х = з. (Транзитивность.) й) Если х = у, то у = х.
(Симметричность.) й») х с— в х. (Рефлексивность.) (Сравните это определение с определением отношения частичного упорядочения. предложенного в разделе 2.2,3. Они сильно различаются несмотря на совпадение двух из трех условий.) Примерами отношений эквивалентности являются отноше- ния "=", отношение конгруэнтности (по модулю гп) для целых чисел, отношение подобия между деревьями, которое определяется в разделе 2.3.1, и т. д. Задача эквивалентносън заключается в считывании нескольких пар эквивалентных элементов н определении с их помощью эквивалентности двух заданных элементов. Например, предположим, что множество о' содержит элементы (1,2,3,4,5,6, 7,8,9) и что даны пары 1=о, 6=8, 7=2, 9=8, 3=7, 4=2, 9ээ 3.
(11) Тогда отсюда следует, например, что 2 эз 6, так как 2 = 7 = 3 = 9 = 8 = 6. Но при этом нельзя установить, справедливо лн утверждение, что 1 : — 6. Действительно, пары (11) делят множество о на два таких класса (12) (1,5) и (2,3,4,6,7,8,9), что два элемента будут эквивалентны тогда и только тогда, когда они принадлежат одному классу. Нетрудно доказать. что любое отношение эквивалентности разбивает множество о' на такие непересекающиеся класси экаиаалентносгли (едигоа!енсе с!аггее), что два элемента будут эквивалентны тогда и только тогда, когда сне принадлежат одному и тому же классу.
Следовательно, решение задачи эквивалентности заключается в определении классон эквивалентности типа (12). Для этого можно начать с ситуации, когда каждый элемент по отдельности образует собственный класс: (13) (1) (2) (3) (4) (5) (6) (7) (8) (9). Затем, если дано отношение 1 = 5, элементы (1,5) можно разместить вместе в одном классе. После обработки первых трех отношений 1 ээ 5, 6 = 8 и 7 = 2 вместо исходного набора классов (13) получим (14) (1,5) (2,7) (3) (4) (6,8) (9). На основе отношения 9 = 8 разместим в одном классе элементы (6,8.,9) и т.
д. Теперь наша задача состоит в поиске удобного способа представления ситуаций наподобие (12)-(14) внутри компьютера для того, чтобы можно было эффективно выполнять операции слияния классов и проверки принадлежности двух заданных элементов одному классу. Для этого в приведенном ниже алгоритме используются ориентированные древовидные структуры. В нем предполагается, что элементы множества о' являются узлами ориентированного леса. Причем два узла эквивалентны вследствие эквивалентности считанных ранее пар тогда и только тогда, когда они принадлеэюат одному дереву. Эту проверку можно довольно просто выполнить, так как два элемента принадлежат одному и тому же дереву тогда и только тогда, когда они являются наследниками одного корня. Более того, слияние двух ориентированных деревьев легко выполняется за счет простого присоединения одного дерева в качестве нового поддерева к корню другого дерева.
Алгоритм Е (Обработка отношений эквивалентности). Пусть о является множеством чисел (1, 2,..., п) и пусть РАЯЕИТ(Ц., РАЕЕИТ[2), ..., РАИЕИТ(п) являются целочисленными переменными, В качестве ввода в этом алгоритме используется множество отношений наподобие (11), а для представления множества ориентированных деревьев используется таблица РАЕЕИТ, так что два элемента считаются РАКЕМТ(1:]: й: 5 О О О О 8 2 О 8 1 2 3 4 5 6 7 8 9' (15) которьк нргдс н<вля<от такие д<'ренья: ~ З Я ~з Л (16) С этого люментн обработка остшн,ных отношений (11) представляется особенно интересной (см. упр. 9).
На практике задача эквивалентности возникает довольно часто. В разделе 7.4.1 прн изучении < в«злости графов Г<удут рас< мотрсны некоторыс существенные усовершенстнона<ши алгоритма Е. В бол<е общей формулировке эта задача встречается Орн обработк< компилятором "обьянленкй эквивалентности" в языках наподобие РВ«ВТ11ЛХ, которая подробно обсуждается в упр. 11. Полшмо пер<"и<ел< нных, существует несколько других способов представления деревьев н памяти компьютера.
Напомним трн основных метода представления линейных снигкон, которые р;нтматрнвались вьнне, в разделе 2.2: простейший однонацрлвлсшп <й сиисок с концевой связью Л, циклически связанные списки и дважды связанные списки. Представление непрошитых бинарных деревьев, рассмотренных в разделе 2.3.1, соответствует простейшему предслввленню на основе как полей 1Д.1МК, так и полей 31.1МК. Восемь других представлений бинарных деревьев можно получить независимо, используя любой из этих трех методов на основе полей 1Д.1МК эквивалентнымн вгледствне заданных отношений эквивалентности тогда н только тогда, когда они относятся к одному и тому же дереву.
(Замечание. В более общем случае элементы множества Я могут быть представлены в виде символьных имен, а не нросто в виде набора <игел от 1 до н. Тогда программа поиска, которая более нодробно описывается в главе 6, нашла бы узлы, соответствующие элеме<гшм множества 3. а элемент таблицы РАКЕМТ соответствовал бы полю в этих узлах. М(однфикяция данного алгоритма для такого более общего случая может быть вьнюлнена достато шо просто.) Е1.
[Иницнллиза<~<я.[ Установить РАКЕМТ(Ц +- О для 1 < Й ~ н. [Это значит„что вге деревья и исходном состоянии годержат только корень, как в (13).) Е2. [Ввод новой нары ] Получи гь следующу<о пару эквивалентных элементов "7' = /с" из входного потока. Если входной ноток исчернан, прекратить выполнение алгоритма. ЕЗ. [Поиск кори«'1<.] Если РАККМТ(у] > О, установить | < — РАККМТ(7] и повторить этот шнг. Е<ши РАККМТЫ > О, установить, й +- РАККМТ[Й] и повторить этот шаг. (По<ш< выполнения операции ] и А переходят к корням двух дереньев, которые ел<сдует сделать эквивалентными. Отношение на входе ] = А избыточно тогда и только тогда, когда ] = Ас) Е4. [Слияние дгр<'вьгв [ Если ] ф 13 установить РАККМТ(]] + — Й.
Вернуться к шагу Е2. $ Читателю р<комгцдтгтгя применить этот алгоритм цо отношению к входному потоке (11). По<же обрлГ>откн отношений 1 г— в 5, 6 = 8, 7 = 2 и 9 = 8 получим соответствия Рис. 27. Кольцевая структура. и НЕ1НЕ. Например, на рис. 27 показан результат циклического связывания, которое применяется в обоих направлениях. Прн использовании циклических связей в обоих направлениях так, как показано на этом рисунке, мы получим кольцевую стрдктурд (ппд лггис1иге). Они оказались достаточно гибкими для целого ряда приложений. Оптимальный выбор представления зависит, как обычно, от типов операций вставки, удаления и обхода, которые необходимы в алгоритмах обработки таких структур. Читателю, который внимательно изучил приведенные выше примеры нз этой главы, будет нетрудно выбрать и применить на практике какой-.либо из вариантов представления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
