AOP_Tom1 (1021736), страница 91
Текст из файла (страница 91)
Таким образом, получаем ь(Рь) = (ьР)* = Р, е(Р») = (»Р)э = Р и »(Р») = (»Р)» = Р. В качестве примера использования этих обозначений предположим, что 1МРО(Р) †э буква, изображенная в узле МООЕ(Р) дерева (2). Тогда, если Р указывает на его корень, получим 1МРО(Р) = А, 1ИРО(Р*) = В, 1ИРО(РЕ) = Е, 1МРО(»Р) = В, 1МРО(»Р) = С и Р» = ьР = 1.ОС(Т), Здесь у читателя может возникнуть чувство неуверенности в отношении правильности приведенных значений Р», Р» и т. д. Однако по мере изучения дальнейшего материала они станут более понятными, в частности для этого полезно выполнить упр. 16,приведенное в конце раздела. Символ "э" в обозначении "Рз" Для и = О это утверждение очевидно выполняется, как следствие шага Т2.
Если и > О, пусть Ро является значением указателя Р в начале шага Т2. Так как Ро ЭА Л, выполним шаг ТЗ, что для стека А означает его изменение с приведением к новому состоянию с элементами А[Ц...А[т)Ре, а Р равняется ШМК(рс). Теперь левое поддерево имеет меньше и узлов, а потому по индукции выполним обход левого подлерева в симметричном порядке и перейдем к шагу Т4 со стеком, содержание которого равно А [Ц, .. А [т] Ро. На шаге Т4 стек возвращается в исходное состояние АШ ..А[т), а Р» — Ре.
На шаге Тб выполняется обход узла МООЕ(ре) и устанавливается значение Р +- ЕЕ1ИК(Ре). Теперь правое поддерево имеет менее и узлов и по индукции совершаем обход правого поддерева в симметричном порядке с переходом к п»агу Т4. Таким образом выполнен обход всего дерева в симметричном порядке согласно определению этого порядка.
Доказательство завершено. Практически идентичный алгоритм можно сформулировать для обхода бинарных деревьев в прямом порядке (см. упр. 12), Несколько сложнее выглядит алгоритм обхода в обратном порядке (см. упр. 13), а потому подобный порядок не имеет такого большого значения, как два других. Для указания узлов-последователей и узлов-предшественников в алгоритмах обхода бинарных деревьев удобно применять следующие обозначения. Если Р указывает на узел бинарного дерева, то представляет букву Б в английском написании термина "симметричный порядок" (вупппесйс огбег). Существует еще однц альтернативный вариант представления бинарных деревьев (2) в памяти компьютера, который отличается от предыдущего способа так же, как циклические списки отличаются от линейных однонаправленных списков. Обратите внимание на то, что в дереве (2) пустых связей содержится больше, чем всех остальных; и действительно, это верно для любого дерева, представленного с помощью обычного метода (см.
упр. 14). На самом деле вряд ли стоит из-за этого так неэкономно расходовать пространство памяти. Вместо этого можно было бы, например, хранить в каждом узле некий двухбитовый "признак" (саК) того, что узел содержит либо пустую, либо непустую связь 1.ЫИК (или КК1МК), либо обе пустые, либо обе непустые связи. В таком случае высвободившееся пространство в памяти, которое прежде использовалось для концевых связей, можно применять в других целях. Хитроумный способ экономного использования памяти предложен А. Дж. Перлисом и Ч.
Торнтоном, которые придумали метод прошипюго (1Лггадед) представления бинарного дерева. В этом методе концевые связи заменяются "нитями" (гйгеадг) которые связаны с другими частями дерева для упрощения его обхода. Прошитое дерево, которое эквивалентно дереву (2), выглядит так: (7) Обычное представление 1.ЫКК(Р) = Л 1.ЫМК(Р) = Ц ф Л КЫРК(Р) = Л КЫНЫК(Р) = Ц ф Л Прошитое представление СТАС(Р) = 1, КК1МК(Р) = ЗР 1.ТАС(Р) = С, 1.ЫИК(Р) = Я КТАС(Р) = 1, КЫРК(Р) = РЭ КТАС(Р) = О, й).1КК(Р) = Ц Здесь пунктиром обозначены "нити", которые всегда направлены к более высокому узлу дерева.
Каждый узел теперь имеет две связи: одни узлы, например С, имеют две обычные связи с левым и правым поддеревьями, другие узлы, например Н,— две связи в виде нитей, а третьи — по одной связи каждого типа. Особые нити, которые выходят из узлов 1) и,), будут рассмотрены ниже. Они появляются в крайнем слева и крайнем справа узлах. Для представления прошитого бинарного дерева в памяти необходимо ввести обозначения, чтобы можно было отличить пунктирные и сплошные связи. Это может быть сделано, как предполагалось выше, с помощью двух дополнительных однобитовых полей в каждом узле, ЬТАС и КТАС.
Тогда прошитое представление можно определить, например, следующим образом. Произвольное (с Произвольное й Рис. 24. Общая ориентация девых и правых связей-нитей и прошитом бинарном дереве. Волнистые линии обозначают связи с другими частями дерева (или ведущие к ним нити). Согласно этому определению каждая новая связь-нить указывает непосредственно на узел-предшественник или узел-последователь конкретного узла в заданном симметричном порядке.
На рис. 24 показана общая ориентация связей-нитей в любом бинарном дереве. В некоторых алгоритмах гарантируется, что корень любого поддерева всегда располагается в ячейках памяти, которые находятся в памяти ниже других узлов этого поддерева. В таком случае 1.ТАС(Р) будет равно 1 тогда и только тогда, когда ЬЬ1МК(Р) < Р, поэтому поле ЬТАС, как и поле КТАС, будет содержать избыточную информацию. Значительным преимуществом прошитых деревьев является то, что алгоритмы обхода для них су щественно упрощаются. Например, с помощью приведенного ниже алгоритма можно вычислить Рь по заданному значению Р. Алгоритм Б (Симметричный (центрированный) узел-последователь в прошитом бинарном дереве). Если Р указывает на узел прошитого бинарного дерева, то данный алгоритм устанавливает Ц +- Рь.
81. (КЫКК(Р) — это нить?~ Установить Ц е — КЫнК(Р). Если КТАС(Р) = 1, прекра- тить выполнение алгоритма. 82. ~Поиск слева.) Если ЬТАС(Ц) = О, установить Ц ь- ЬЫМК(Ц) и повторить этот шаг. В противном случае прекратить выполнение алгоритма. 1 Обратите внимание на то, что для его выполнения не потребуется стек, который прилгенялся в алгоритме Т: Действительно, с помощью обычного представления (2) невозможно найти РЭ столь.же эффективным путем, зная только адрес Р произвольно выбранного узла дерева. Поскольку в обычном представлении бинарного дерева нет направленных вверх связей, то нет и сведений о том, какие узлы расположены выше, если только не сохранять информацию о пути к данному узлу.
Стек в алгоритме Т используется как раз для хранения этой информации при отсутствии нитей. Алгоритм Б назван эффективным, хотя это свойство не всегда очевидно, поскольку шаг 82 может выполняться достаточно много раз.. Может быть, вместо многократного повторения шага 52 для ускорения процесса следовало бы использовать стек, как в алгоритме Т? Для исследования этого вопроса выясним, сколько раз в среднем выполнялся шаг 82, если Р указывает "произвольный" узел дерева, или, что то же самое, определилг общее количество выполнений шага 32, если алгоритм Б повторно используется для обхода всего дерева.
Выполняя этот анализ, полезно будет также познакомиться с программами, в которых реализованы алгоритмы Б и Т. Как обычно, при разработке алгоритмов следует учесть возможность их применения для пустых бинарных деревьев, и, если Т является указателем данного дерева, желательно, чтобы СОС(Т) * и ЕОС(Т) э были первыми узлами и прямом и симметричном порядках соответственно. Для прошитых деревьев узел МООЕ(ЕОС(Т)) удобно преобразовать в "заголовок списка" для дерева со следующими параметрами: ШМК(НЕАО) = Т, НЕ1МК(НЕАО) = НЕАО, СТАС(НКАО) = 0) НТАС(НЕАО) = О. (8) (Здесь НЕАО обозначает 1ОС(Т), т. е. адрес заголовка списка.) Пустое прогпитое дерево удовлетворяет условиям ШМК(НЕАО) = НЕАО, СТАС(НЕАО) = 1.
Заголовок Дерево растет за счет вставки узлов слева от заголовка списка. (Эти начальные условия преимущественно продиктованы алгоритмом вычисления Р*, который рассматривается в упр. 17.) В соответствии с этими соглашениями прошитое представление бинарного дерева (1) для компьютера будет выглядеть так: После описания предварительных сведений можно приступать к созданию программ для компьютера ИТХ, предназначенных для реализации алгоритлюв Б н Т. В приведенных ниже программах предполагается, что узлы бинарного дерева состоят из двух глов: В непрошитом дереве СТАО и КТАО всегда будут равны "+", а концевые связи будут представлены нулем.
В прошитом дереве знак "+" используется для меток„которые равны О, а знак "-" — для меток, которые равны 1. Обозначения СЕ1МКТ и НЕ1ИКТ будут использоваться для полей СТАО-СС1ХК и НТАО-ЕС1ИК соответственно. Два бита метки занимают знаковые ячейки слова в памяти компьютера М1Х, которые ни для чего другого все равно не используются, а потому они не занимают лишнего места в памяти. Аналогично в компьютере ИМ1Х можно было бы "бесплатно" использовать младшие биты полей связи в качестве битов метки, поскольку указатель обычно принимает четные значения, а также потому что при адресации памяти в компьютере ММ1Х проще игнорировать именно младшие биты.
В следующих двух программах выполняется обход бинарного дерева в симметричном (т. е. центрированном) порядке с периодическигяи переходами к ячейке Ч151Т, в то время как индексный регистр 5 уклзывает на текущий узел. Программа Т. В этой реализации алгоритма Т стек находится в ячейках А + 1, А + 2, ..., А + МАХ; г16 является указателем стека и г15 я Р. Событие переполнения (ОУЕИРСОЫ) происходит при недопустимом возрастании размеров стека. Эта програгима незначительно отличается от алгоритма Т (шаг Т2 в нем встречается трижды), поэтому не нужно проверять, пуст ли стек, при переходе от шага ТЗ к шагу Т2, а затем — к шагу Т4.
~И.У 1 Стоп, если Р = Л. ) 1 1 1 О! СС1ИК 02 К!.1МК 08 Т1 04 Т2А 05 06 ТЗ 07 08 09 !О !! Т2В !2 Т4 !8 !4 Т5 !5 !6 Т2С !7 !6 РОМЕ ЕЦО 1:2 ЕЦО 1:2 !.Вб НЕАВ(ШХК 052 ВОХЕ ЕХТб О ВЕСб МАХ 06МИ ОЧЕХРЬОЫ 1ИСб МАХ+1 5Т5 А,б СВ5 0,5(СЕТИК) 05ИХ ТЗ ЬВ5 А,б ВЕСб 1 ЗМР Ч151Т СВ5 1,5(НС1МК) 35ИХ ТЗ 05ИЗ Т4 ТЗ. Стек с Р. Емкость стека исчерпана? Если нет, увеличить указатель стека. Сохранить Р в стеке. Р +- Ы.1ХК(Р).
Перейти к шагу ТЗ, если Р Р Л. Т4. Р с Стек. Уменьшить указатель стека. Т6. Попасть в Р. Р <-%.1ХК(Р). Т2. Р=Л? Проверить, пуст ли стек. ! Программа Б. Алгоритм Б дополнен условиями инициализации и прекращения выполнения, чтобы его программу можно было сравнить с программой Т. ЕЦО О:2 ЕЦН О:2 ЕМТ5 НЕАР ЛИР 2Г ОНР У151Т ПРЯМ 1,5(НЕ1МКТ) 35ММ 1Р ЕММ6 О,б ЕМТЯ 0,6 106 0,5(ььХМКТ) 36Р 52 ЕМТ6 -НЕАО,Я 16М2 ЯЗ ОХ ЕЕ1МКТ 08 Н1 1МКТ 08 ЯО 04 Об ЯЗ Об 51 07 Об 00 52 10 2Н 11 10 1Н 18 н,ищь ~, у ю. ЯЗ. Попасть в Р. Я1. НАЕИК(Р— это нить? Выполнить переход, если ЗТАС(Р) = 1. В противном случае установить Ц <- Ю.1МК(Р). ЯЗ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
