Д. Кнут - Искусство программирования том 1 (1119450), страница 90
Текст из файла (страница 90)
Событие переполнения (ОЧЕНРРОИ) происходит при недопустимом возрастании размеров стека. Эта программа незначительно отличается от алгоритма Т (шаг Т2 в нем встречается трижды), поэтому не нужно проверять, пуст ли стек, прн переходе от шага ТЗ к шагу Т2, а затем — к шагу Т4. ~И.У Р Стоп, если Р = Л. 01 ЕР1ИК 02 В1.1ИК 05 Т1 04 Т2А 05 05 ТЗ 07 ОВ 09 10 11 Т2В 12 Т4 1Я 14 Т5 15 15 Т2С !7 18 РОМЕ ЕЦО 1:2 ЕЦО 1:2 РР5 НЕАРЖТИК) 1 552 РОМЕ 1 ЕИТ6 0 1 РЕС6 МАХ и 56ИИ ОиЕНРРОИ и 1ИС6 МАХ+1 и ЯТ5 А,б и РР5 0,5(РР1ИК) и 55ИЗ ТЗ и РР5 А,б и РЕС6 1 и 5МР 71Б1Т и РР5 1,5(Н1.1ИК) и 55И2 ТЗ и 56ИХ Т4 а ТЗ.
Стек ~ Р. Емкость стека исчерпана? Если нет, увеличить указатель стека, Сохранить Р в стеке. Р +- 1.1.1МК(Р). Перейти к шагу ТЗ, если Р ~ Л. 74. Р ~ Стек. Уменьшить указатель стека. Т5. Попасть в Р. Р Ф- Ю.1МК(Р). Т2. Р=Л? Проверить, пуст ли стек. 1 Программа Б. Алгоритм Б дополнен условиями инициализации и прекращения выполнения, чтобы его программу можно было сравнить с программой Т. 01 1Е1ИКТ 02 Н(.1МКТ Об ЯО 04 Об ЯЗ Об 51 07 08 00 52 10 2Н 11 12 1Н 10 Е00 0:2 ЕЦО О:2 ЕМТ5 НЕАР ОМР 2Р ЗМР ((1511 ЫЯИ 1,5(Н51МКТ) 25МИ 1Р ЕММ6 0,5 ЕИТ5 0,6 Жб 0,5((.Е1ИКТ) 26Р 52 ЕИТ6 -НЕА0,5 36ИЕ ЯЗ Н.эиэ~и .у Р и. ЯЗ.
Попасть в Р. 51. Ш.1МК(Р— это нить? Выполнить переход, если АТАО(Р) = 1. В противном случае установить Ц <- Яь1МК(Р). 52. Поиск слева. Установить Р э- О. О +- 1.1.1МКТ(Р). Если 1.ТАС(Р) = О, повторить. и и+1 и+1 и+1 и+1 Переход х шагу ЯЗ (необходимо попасть в Р), если Р ~ НЕАР. В приведенном выше коде показано также время выполнения отдельных команд, которое легко определить по закону Кирхгофа и следующим правилам.
!) В программе Т количество вставок в стек должно равняться количеству удалений. Н) В программе Б поля 551МК и НИИК каждого узла проверяются только однажды. тй) Количество "посещений" (г(э(сэ) равно количеству узлов дерева. Анализируя программу Т, получим, что для ее выполнения потребуется 15и+ а+ 4 единиц времени, а для программы Б — 11п — а + 7, где и — количество узлов в дереве, а — количество правых концевых связей (т. е. количество узлов без правого поддерева). Предполагая, что п ф О, получим, что число а может варьироваться от 1 до и. А если допустить существование симметрии меясду правой и левой сторонами дерева, то в таком случае среднее значение а будет равно (и+ 1)/2.
Доказательство данного результата приводится в упр. 14. На основе этого анализа можно сделать следующие принципиальные выводы. 1) Если Р— произвольно выбранный узел дерева, то щаг Б2 в среднем выполняется только однажды эа все время работы алгоритма Б. й) Обход прошитого дерева происходит несколько быстрее, поскольку для него не нужно выполнять операции со стеком.
Ш) Для алгоритма Т требуется немного больше памяти, чем для алгоритма Б, из-за использования вспомогательного стека. В программе Т стек хранится в последовательных ячейках памяти, значит, на его размер следует наложить какое-то ограничение. При превышении этого ограничения могут возникнуть крайне нежелательные последствия, поэтому его следует выбрать достаточно большим (см. упр. 10).
Поэтому требования к памяти со стороны программы Т существенно выше, чем со стороны программы Б. Часто в сложных программах нужно независимо выполнить обход сразу нескольких деревьев, и в каждом таком случае для работы программы Т понадобится отдельный стек. Это предполагает использование в программе Т связанного распределения для его стека (см, упр. 20). В такой ситуации время выполнения становится равным 30п+ а+4 единицам. что приблизительно вдвое медленнее. Однако время обхода дерева может оказаться не таким уж и важным, если приходится учитывать еще и время выполнения другой сопрограммы.
Еще один альтернативный вариант основан на хитроумном способе хранения внутри самого дерева связей стека (см. упр. 21). !г) Алгоритм В, конечно, имеет более общий вид, чем алгоритм Т, поскольку он позволяет сразу пройти от Р к Рэ, когда нет необходимости совершать обход всего бинарного дерева. Таким образом, прошитое бинарное дерево в отношении задачи обхода дерева обладает несомненными преимуществами по сравнению с непрошитым бинарным деревом. В некоторых приложениях эти преимущества практически сводятся на нет из-эа несколько увеличенного времени выполнения вследствие вставки и удаления узлов в прошитом дереве.
Иногда дополнительную экономию памяти можно получить за счет "совместного использования" общих поддеревьев с непрошитым представлением, тогда как для прошитых деревьев потребуется строго соблюсти древовидную структуру без какого-либо перекрытия поддеревьев. Связи-нити также могут использоваться для вычисления Р*, эР и эР, причем эффективность такого вычисления будет сравнима с эффективностью алгоритма б.
Функции *Р и Р~ несколько труднее вычислитьэ поскольку они предназначены для непрошнтых представлений дерева. Читателю настоятельно рекомен,чуется выполнить упр. 17. Преимущества прошитых деревьев могли бы быть утрачены в основном из-за сложности установления связей-нитей. Однако именно простота организации роста прошитых деревьев, которая реализуется почти так же легко. как и в случае роста обычных деревьев, определяет работоспособность данной идеи. В качестве примера рассмотрим следующий алгоритм. Алгоритм 1 [Всглавка в прошитое бинарное дерево).
Этот алгоритм присоединяет один узел, МОВЕ(Ц), в качестве правого полдерева узла МОРЕ(Р), если правое поддерево пусто [т. е. если НТАС(Р) = 1). В противном случае узел МОРЕ(Ц) вставляется между узлами МОВЕ(Р) и ИОВЕ(НВ1ИК(Р)) и последний из них становится правым ребенком узла МОРЕ (Ц) . Предполагается, что бинарное дерево, в которое вставляется новый узел, является прошитым, как в (10). Один иэ вариантов этого алгоритма рассматривается в упр. 23.
11. [Инициализация признаков и связей.] Установить НЕ1МК(Ц) е — НЕ1МК(Р), НТАС(Ц) < — НТАС(Р), НВ1ИК(Р) е — Ц, НТАС(Р) е — О, ьь1МК(Ц) +- Р, БОТАС(Ц) е — 1. 12. [Является лн НЕ1МК(Р) нитью?] Если НТАС(ц) = О, установить ЕВ1МК(Цэ) < — Ц. (Здесь Цэ определяется алгоритмом Б, который будет работать правильно, даже если ШМК(Цэ) теперь указывает на узел МОВЕ(Р), а не на узел МОВЕ(ц). Этот шаг необходим при вставке узла в середину прошитого дерева, а не при добавлении нового листа.) Поменяв местами левую и правую стороны (например, обозначение Цэ заменяя обозначением ьЦ на шаге 12), получим аналогичный алгоритм для вставки узла слева.
До сих пор рассматривачигь бинарные деревья. в которых связи-нити проводились слева и справа. Однако су.ществует еще одно важное представление, которое занимает промежуточное положение между непрошитым и полностью прошитым представлениями. Так называемое правопрошитое бинарное дерево (пуМ-гЛгеайеК Ипату й ее) представляет собой комбинацию этих двух подходов за счет использования правых связей-нитей Йь1МК, тогда как пустые левые поддеревья представлены связями-нитями Ь~.1МК = й. (Аналогичным образам устроено левопрошитое бинарное дерево, но только в нем пустыми являются связи-нити ШМК.) В алгоритме В связи-нити ЬЬ1МК практически не используются, поэтому, если заменить условие БОТАС = 0 на шаге Б2 условием 11.1МК ~ А, получим алгоритм обхода правопрошитого бинарного дерева в симметричном порядке.
Причем программа Б может без каких- либо изменений работать с правопрошитыми бинарными деревьями. Для очень многих приложений бинарных древовидных структур требуется выполнять обход дерева только слева направо с помощью функций Рэ и/или Р*, и потому для этих приложений нет необходимости прошивать связи-нити Ь~.1МК. Здесь рассмотрены случаи обхода в обоих направлениях (правом и левом) для того, чтобы указать на симметрию данной ситуации и ее возможности, но на практике прошивку гораздо чаще требуется выполнять только с одной стороны. Рассмотрим теперь еще одно важное свойство бинарных деревьев и их связь с проблемой обхода узлов дерева. Говорят, что два бинарных дерева Т и Т' подобны, если они имеют одинаковую структуру. Формально это значит, что либо (а) они оба пусты, либо (Ь) они оба не пусты, а их левое и правое поддеревья подобны соответственно.
Иначе говоря, подобие означает, что схемы деревьев Т и Т' имеют одинаковую "форму". Другими словами, подобие означает наличие взаимно однозначного соответствия между узлами деревьев Т и Т' с сохранением структуры. Если узлы и~ и ит дерева Т соответствуют узлам и', и ит дерева Т', то узел и~ находится в левом поддереве из тогда и только тогда, когда узел и', находится в левом поддереве иэ.
Это утверждение верно и для правых поддеревьев. Бинарные деревья Т и Т' называются эквивалентиммп (едвгаа1еп1), если они подобны и соответствующие узлы содержат одинаковую информацию. Формально пусть ш1о(и) обозначает информацию, которая содержится в узле и; в таком случае деревья эквивалентны тогда и только тогда, когда либо (а) они оба пусты, либо (Ь) они оба не пусты и ш1о(корень(Т)) = ш1о(корень(Т')), а их левые и правые поддеревья соответственно эквивалентны.
В качестве примера этих определений рассмотрим <ледующие четыре бинарных дерева: Первые два из них не являются подобными. Второе, третье и четвертое — подобны, а второе и четвертое †эквивалент. В некоторых приложениях, использующих древовидные структуры, необходимо определить подобие или эквивалентность бинарных деревьев, Для этого полезно рассмотреть следующую теорему. Теорема А. Пусть ! ! ! и!, иш, и„и и„ил,..., иь являются узлами бинарных деревьев Т и Т' соотнетствеяно в прямом порядке обхо- да. Для любого узла и положим 1(и) = 1, если и имеет непустое левое поддерево, иначе Ии) = 0; (11) т(и) = 1! если и имеет непустое правое поддерево, иначе г(и) = 0; Следовательно, Т и Т' подобны тогда и только тогда, когда п = и' и 1(и,) = ((и,), г(и,) = г(и,') для 1 < у < и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
