AOP_Tom1 (1021736), страница 92
Текст из файла (страница 92)
Поиск слева. Установить Р ь- Ц. а +- 111МКТ(Р). Если 1.ТАС(Р) = О,повторить. п и+1 и+1 и+1 п+1 Переход к шагу ЯЗ (необходимо попасть в Р), если Р Ф НЕАО А В приведенном выше коде показано также время выполнения отдельных команд, которое легко определить по закону Кирхгофа и следующим правилам. 1) В программе Т количество вставок в стек должно равняться количеству удалений. Н) В программе Я поля ШМК и НПМК каждого узла проверяются только однажды. ш) Количество "посещенийь (т)э(сэ) равно количеству узлов дерева.
Анализируя программу Т, получим, что для ее выполнения потребуется 15п + а+ 4 единиц времени, а для программы Б — 11п — а + 7, где и — количество узлов в дереве, а — количество правых концевых связей (т. е. количество узлов без правого подлерева). Предполагая, что и ф О, получим, что число а может варьироваться от 1 до и.
А если допустить существование симметрии между правой и левой сторонами дерева, то в таком случае среднее значение а будет равно (и+ 1)/2. Доказательство данного результата приводится в упр. 14. На основе этого анализа можно сделать следующие принципиальные выводы. 1) Если Р— произвольно выбранный узел дерева, то шаг Я2 в среднем выполняется только одиалсдм за все время работы алгоритма Я. Н) Обход прошитого дерева происходит несколько быстрее, поскольку для него не нужно выполнять операции со стеком. ш) Для алгоритма Т требуется немного больше памяти, чем для алгоритма Я, из-за использования вспомогательного стека.
В программе Т стек хранится в последовательных ячейках памяти, значит, на его размер следует наложить какое-то ограничение. При превышении этого ограничения могут возникнуть крайне нежелательные последствия, поэтому его следует выбрать достаточно большим (см. упр. 10). Поэтому требования к памяти со стороны программы Т существенно выше, чем со стороны программы Я. Часто в сложных программах нужно независимо выполнить обход сразу нескольких деревьев, и в каждом таком случае для работы программы Т понадобится отдельный стек. Это предполагает использование в программе Т связанного распределения для его стека (см. упр, 20). В такой ситуации время выполнения становится равным ЗОп+ а+4 единицам. что приблизительно вдвое медленнее.
Однако время обхода дерева может оказаться не таким уж и важным, если приходится учитывать еще и время выполнения другой сопрограммы. Еще один альтернативный вариант основан на хитроумном способе хранения внутри самого дерева связей стека (см. упр. 21). ьх) Алгоритм 5, конечно, имеет более общий вид, чем алгоритм Т, поскольку он позволяет сразу пройти от Р к РЭ, когда нет необходимости совершать обход всего бинарного дерева. Таким образом, прошитое бинарное дерево в отношении задачи обхода дерева обладает несомненными преимуществами по сравнению с непрошитым бинарным деревом.
В некоторых приложениях эти преимущества практически сводятся на нет из-за несколько увеличеныого времени выполнения вследствие вставки и удаления узлов в прошитом дереве. Иногда дополнительную экономию памяти можно получить за счет "совместного использования" общих поддеревьев с непрошитым представлением, тогда как для прошитых деревьев потребуется строго соблюсти древовидную структуру без какого-либо перекрытия поддеревьев.
Связи-нити также могут использоваться для вычисления Р*, ЭР и 1Р, причем эффективность такого вычисления будет сравнима с эффективностью алгоритма В. Функции еР и Р1 несколько труднее вычислить, поскольку они предназначены для непрошитых представлений дерева. Читателю ыастоятельыо рекомендуется выполнить упр. 17. Преимущества прошитых деревьев могли бы быть утрачены в основном из-за сложности установления связей-нитей. Однако именно простота организации роста прошитых деревьев, которая реализуется почти так же легко.
как и в случае роста обычных деревьев, определяет работоспособность данной идеи. В юшестве примера рассмотрим следующий алгоритм. Алгоритм 1 (Вставка в прошитое бинарное дерево). Этот алгоритм присоединяет один узел, МОСЕ(Ц), в качестве правого поддерева узла МООЕ(Р), если правое поддерево пусто (т. е, если БОТАС(Р) = 1). В противном случае узел ИООЕ(Ц) вставляется между узлами МООЕ(Р) и ИООЕ(КЕ1ИК(Р)) и последний из них становится правым ребенком узла МООЕ1Ц). Предполагается, что бинарное дерево, в которое вставляется новый узел, является прошитым, как в (10). Один из вариантов этого алгоритма рассматривается в упр. 23.
11. 1Инициализация признаков и связей.] Установить КЕ1ИК(Ц) в- КЕ1МК(Р), КТАС(Ц) е- БОТАС(Р), КПМК(Р) < — Ц, КТАС(Р) +- О, 1Л 1МК(Ц) + — Р, БОТАС(Ц) е- 1. 12. (Является ли Н1.1МК(Р) нитью71 Если БОТАС(Ц) = О, устаыовить ЕЕ1МК(Цз) + — Ц. (Здесь Цэ определяется алгоритмом Б, который будет работать правильно, даже если Е1.1МК(Цэ) теперь указывает ыа узел ИООЕ(Р), а не ыа узел ИООЕ(Ц).
Этот шаг необходим при вставке узла в середину прошитого дерева, а не при добавлении нового листа.) Поменяв местами левую и правую стороны (например, обозыачение Цэ заменяя обозначением ьЦ на шаге 12), получим аналогичный алгоритм для вставки узла слева. До сих пор рассматривались бинарные деревья, в которых связи-пити проводились слева и справа. Однако существует еще одно важное представление, которое занимает промежуточное положение между непрошитым и полностью прошитым представлениями.
Так нвЛываемое правопрошипюе бинарное дерево (пдйс-гЬгеайед Ь~вагу 1гее) представляет собой комбинацию этих двух подходов за счет использования правых связей-нитей Кь1ИК, тогда как пустые левые поддеревья представлены связями-нитями ШИК = Л. (Аналогичным образом устроено левопрошитое бинарное дерево, но только в нем пустыми являются связи-нити ШИК.) В алгоритме В связи-нити ШИК практически не используются, поэтому, если заменить условие 1.ТАС = О на шаге 52 условием ШИК ф й, получим алгоритм обхода правопрошитого бинарного дерева в симметричном порядке.
Причем программа В может без каких- либо изменений работать с правопрошитыми бинарными деревьями. Для очень многих приложений бинарных древовидных структур требуется выполнять обход дерева только слева направо с помощью функций Рэ и/или Р*, и потому для этих приложений нет необходимости прошивать связи-нити ШИК. Здесь рассмотрены случаи обхода в обоих направлениях (правом и левом) для того, чтобы указать на симметрию данной ситуации и ее возможности, но на практике прошивку гораздо чаще требуется выполнять только с одной стороны.
Рассмотрим теперь еще одно важное свойство бинарных деревьев н их связь с проблемой обхода узлов дерева. Говорят, что два бинарных дерева Т и Т' подобны, если они имеют одинаковую структуру. Формально это значит, что либо (а) они оба пусты, либо (Ь) они оба не пусты, а их левое и правое полдеревья подобны соответственно. Иначе говоря, подобие означает, что схемы деревьев Т и Т' имеют одинаковую "форму". Другими словами, подобие означает наличие взаимно однозначного соответствия между узлами деревьев Т и Т' с сохранением структуры.
Если узлы и~ и ит дерева Т соответствуют узлам и', и пэ дерева Т', то узел и~ находится в левом поддереве ит тогда и только тогда, .когда узел и', находится в левом поддереве ит, Это утверждение верно и для правых поддеревьев. Бинарные деревья Т и Т' называются эквивалентными (ееийа1еп1), если они подобны и соответствующие узлы содержат одинаковую информацию. Формально пусть шло(и) обозначает информацию, которая содержится в узле и; в таком случае деревья эквивалентны тогда и только тогда, когда либо (а) они оба пусты, либо (Ь) они оба не пусты и!п1о(корень(Т)) = ш1о(корень(Т')), а их левые и правые поддеревья соответственно эквивалентны.
В качестве примера этих определений рассмотрим следующие четыре бинарных дерева: Первые два из ннх не являются подобными. Второе, третье и четвертое — подобны, а второе и четвертое — эквивалентны. В некоторых приложениях, использующих древовидные структуры, необходимо определить подобие или эквивалентность бинарных деревьев. Для этого полезно рассмотреть следующую теорему. Теорема А. Пусть ! и! из ° °,иа и иыиш... иа являются узлами бпнарных деревьев Т н Т' соответственно в прямом порядке обхо- да.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
