Д. Кнут - Искусство программирования том 1 (1119450), страница 98
Текст из файла (страница 98)
Прошитое дерево-предоставляет возможность перехода к верхним узлам, хотя и с небольшой скоростью. Однако иногда лучше иметь в каждом узле третью связь РАЕЕИТ. При ее наличии получим трижды связанное дерево (1тр!у 1тйеИ 1гее), каждый узел которого имеет связи ЕСН1ьй, Ы.1ИК н РАИЕИТ. На рис. 26 показано, представление трижды связанного дерева для (2), а пример его использования приводится в разделе 2.4. Рнс.
26. Трижды связанное дерево Ясно, что связи РАНЕИТ самой по себе достаточно для полного описания структуры любого ориентированного дерева (нли леса), поскольку схему любого дерева можно нарисовать, зная все направленные вверх связи. Каждый узел, за исключением корня, имеет только одного родителя, но может иметь сразу несколько детей.
Поэтому для их определения проще использовать связи, направленные вверх, а не вниз. Почему же тогда они до сих пор не рассматривалнсь? Ответ, конечно же, заключается в том, что направленные вверх связи не всегда пригодны для используемого приложения, так как лорой очень трудно быстро определить, является ли узел концевым, или найти какого-либо ребенка узла.
Однако есть очень важное приложение, для работы с которым достаточно иметь только связи, направленные вверх. Рассмотрим вкратце элстантный алгоритм обработки отношений эквивалентности, предложенный М, Дж. Фишером (М. 3. Г1всЬег) и Б. А. Галлереи (В. А. Са!1ег). Отношением эквивалентности (еди1иа1епсе ге1а11оп) ": —" называется отношение между элементами множества 5, которое удовлетворяет следующим условиям для любых (необязательно различных) объектов х, у и э множества 5. 1) Если х = у и у = х, то х = э. (Транзитивность.) Н) Если х = у, то у = х. (Симметричность.) ш) х = х. (Рефлексивность.) (Сравните это определение с определением отношения частичного упорядочения. предложенного в разделе 2.2.3.
Они сильно различаются несмотря на совпадение двух из трех утловий.) Примерами отношений эквивалентности являются отноше- иия "=", отношение конгруэнтности (по модулю гп) для целых чисел, отношение подобия между деревьями, которое определяется в разделе 2.3.1, и т. д. Задача эквивалентности заключается в считывании нескольких пар эквивалентных элементов и определении с их помощью эквивалентности двух заданных элементов. Например, предположим, что множество 5 содержит элементы (1,2,3,4,5,6,7,8,9) и что даны пары 7=2, 9=8, Зээ 7, 4гэ 2, 9=3. (11) 6=8, 1=5, Тогда отсюда следует, например, что 2 = 6, так как 2 = 7 = 3 = 9 = 8 = 6.
Но при этом нельзя установить, справедливо ли утверждение, что 1 = 6. Действительно, пары (11) делят множество 5 на два таких класса (12) (1,5) и (2,3,4,6,7,8,9), что два элемента бухнут эквивалентны тогда и только тогда, когда они принадлежат одному классу. Нетрудно доказать, что любое отношение эквивалентности разбивает множество 5 на такие непересекающиеся классы эквивалентности (еди1оа1епсс с1аггсэ), что два элемента будут эквивалентны тогда и только тогда, когда они принадлежат одному и тому же классу. Следовательно, решение задачи эквивалентности заключается в определении классов эквивалентности типа (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) внутри компьютера для того, чтобы можно было эффективно выполнять операции слияния классов и проверки принадлежности двух заданных элементов одному классу. Для этого в приведенном ниже алгоритме используются ориентированные древовидные структуры.
В нем предполагается, что элементы множества 5 являются узлами ориентированного леса. Причем два узла эквивалентны вследствие эквивалентности считанных ранее пар тогда и только тогда, когда они принадлежат одному дсрсау. Эту проверку можно довольно просто выполнить, так как два элемента принадлежат одному н тому же дереву тогда и только тогда, когда онн являются наследниками одного корня. Более того., слияние двух ориентированных деревьев легко выполняется за счет простого присоединения одного дерева в качестве нового поддерева к корню другого дерева.
Алгоритм Е (Обработка отношений эквивалентности). Пусть 5 является множеством чисел (1,2,..., н) и пусть РАЕЕйТ(Ц, РАКЕМТ(2), ..., РАЕЕМТ(н) являются целочисленными переменными. В качестве ввода в этом алгоритме используется множество отношений наподобие (11), а для представления мяожества ориентированных деревьев используется таблица РАЕЕМТ, так что два элемента считаются РАЕЕИТ [ЕП й: 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МК, так и полей Н.1МК.
Восемь других представлений бинарных деревьев можно получить ии>ависнмо, используя любой из этих трех методов на основе полей ЬЕ1МК эквивалс нтными вследста>Се заданных отношений эквивалентности тогда и только тогда, когда опи относятся к одному н тому же дереву. (Замечание. В более общем случае элементы множества 5 могут быть представлены в виде символьных имен, а не просто в виде набора чисел от 1 до п.
Тогда программа поиска, которая более подробно описывается в главе 6, нашла бы узлы, соответствующие элементам множества 5. а элемент таблицы РАЕЕИТ соответствовал бы полю в этих узлах. Мол>сфикац>ся данного алгоритма лля такого более общего случая может быль выполнена лостяточно просто.) Е1. [Ншщивлизация.[ Установить РАЕЕИТ[Ц +- О для 1 < й < и. (Это значит, что вс е деревья и исходном состоянии содержат только корень, как в (13).) Е2. [Ввод новой пары.) Получить следующую пару эквивалентных элементов "7' = >с" из вхолиого потока.
Если входной поток исчерпан, прекратить выполнение алгоритма. Е3. [Псиюк корней.) Если РАЕЕМТ[Я > О, установить 7' +- РАЕЕИТ[Я и повторить этот шиг. Если РАМЕМТ [Ц > О, установить й + — РАЕЕИТ [1) и повторить этот шаг. (После выполнения операции 7 и А переходят к корням двух деревьев, которые слслуст сделать эквивалентными. Отношение на входе 7: — й избыточно тогда и только тогда, когда 7' =' Аэ) Е4. [Слияние Лгревьгв.] Если 7' ф 15 установить РАЕЕИТ[Я с- Й. Вернуться к и>агу Е2.
! Чит>те>по Оскол>с>слус»гся применить этот алгоритм по отношению к входному потоку (11). Пск.и обриботк>л отношений 1:— 5, 6 =: 8, 7 = 2 и 9 = 8 получим соответствии Рис. 27. Кольцевая структура. и 05.1ИК. Например. на рис. 27 показан результат циклического связывания, которое применяется в обоих направлениях. При использовании циклических связей в обоих направлениях так, как показано на этом рисунке, мы получим кольцевую структуру (гшд Игиссиге). Онн оказались достаточно гибкими для целого ряда приложений. Оптимальный выбор представления зависит, как обычно, от типов операций вставки, удаления и обхода, которые необходимы в алгоритмах обработки таких структур. Читателю, который внимательно изучил приведенные выше примеры из этой главы, будет нетрудно выбрать и применить на практике какой-либо из вариантов представления.
В заключение раздела приведем пример модифицированной дважды связанной циклической структуры, которая используется для рассмотренной выше задачи, а именно — для полиномивльной арифметики. Алгоритм 2.2.4А выполняет сложение одного полинома с другим прн условии, что оба полинома представлены в виде циклических списков. А остальные алгоритмы того же раздела соответствуют другим операциям над полиномами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
