Программа S. Алгоритм S дополнен условиями инициализации и прекращения выполнения, чтобы его программу можно было сравнить с программой Т.

В приведенном выше коде показано также время выполнения отдельных команд, которое легко определить по закону Кирхгофа и следующим правилам.

i) В программе Т количество вставок в стек должно равняться количеству удалений.

ii) В программе S поля LLINK и RLINK каждого узла проверяются только однажды.

iii) Количество "посещений" (visits) равно количеству узлов дерева.

Анализируя программу Т, получим, что для ее выполнения потребуется 15п + а + 4 единиц времени, а для программы S - Пп - а + 7, где п - количество узлов в дереве, а - количество правых концевых связей (т. е. количество узлов без правого поддерева). Предполагая, что п / О, получим, что число а может варьироваться от 1 до п. А если допустить существование симметрии между правой и левой сторонами дерева, то в таком случае среднее значение а будет равно (п+ 1)/2. Доказательство данного результата приводится в упр. 14.

На основе этого анализа можно сделать следующие принципиальные выводы.

i) Если Р - произвольно выбранный узел дерева, то шаг S2 в среднем вьшолняется только однажды за все время работы алгоритма S.

ii) Обход прошитого дерева происходит несколько быстрее, поскольку для него не нужно вьшолнять операции со стеком.

iii) Для алгоритма Т требуется немного больше памяти, чем для алгоритма S, из-за использования вспомогательного стека. В програ.мме Т стек хранится в последовательных ячейках памяти, значит, на его размер следует наложить какое-то ограничение. При превышении этого ограничения могут возникнуть крайне нежелательные последствия, поэтому его следует выбрать достаточно большим (см. упр. 10). Поэтому требования к памяти со стороны программы Т существенно выше, чем со стороны программы S. Часто в сложных программах нужно независимо выполнить обход сразу нескольких деревьев, и в каждом таком случае для работы программы Т понадобится отдельный стек. Это предполагает использование в программе Т связанного распределения для его стека (см. упр. 20). В такой ситуации время выполнения становится равным

30n+a+4 единицам, что приблизительно вдвое медленнее. Однако время обхода дерева может оказаться не таким уж и важным, если приходится учитывать еще и время выполнения другой сопрограммы. Еще один альтернативный вариант основан на хитроумном способе хранения внутри самого дерева связей стека (см. упр. 21).

iv) Алгоритм S, конечно, имеет более общий вид, чем алгоритм Т, поскольку он позволяет сразу пройти от Р к Р$, когда нет необходимости совершать обход всего бинарного дерева.

Таким образом, прошитое бинарное дерево в отношении задачи обхода дерева обладает несомненными преимуществами по сравнению с непрошитым бинарным деревом. В некоторых приложениях эти преимущества практически сводятся на нет из-за несколько увеличенного времени вьшолнения вследствие вставки и удаления узлов в прошитом дереве. Иногда дополнительную экономию памяти можно получить за счет "совместного использования" общих поддеревьев с непрошитым представлением, тогда как для прошитых деревьев потребуется строго соблюсти древовидную структуру без какого-либо перекрытия поддеревьев.

Связи-нити также могут использоваться для вычисления Р*, $Р и ttP, причем эффективность такого вычисления будет сравнима с эффективностью алгоритма S. Функции *Р и Pti несколько труднее вычислить, поскольку они предназначены для непрошитых представлений дерева. Читателю настоятельно рекомендуется вьшолнить упр. 17.

Преимущества прошитых деревьев могли бы быть утрачены в основно.м из-за сложности установления связей-нитей. Однако именно простота организации роста прошитых деревьев, которая реализуется почти так же легко, как и в случае роста обычных деревьев, определяет работоспособность данной идеи. В качестве примера рассмотрим следующий алгоритм.

Алгоритм I {Вставка в прошитое бинарное дерево). Этот алгоритм присоединяет один узел, NODE(Q), в качестве правого поддерева узла NODE(P), если правое поддерево пусто (т. е. если RTAG(P) = 1). В противном случае узел NODE(Q) вставляется между узлами NODE(P) и NODE (RLINK (Р)) и последний из них становится правым ребенком узла NODE (Q). Предполагается, что бинарное дерево, в которое вставляется новый узел, является прошитым, как в (10). Один из вариантов этого алгоритма рассматривается в упр. 23.

11. [HHHnHajm3a4HH признаков и связей.] Установить RLINK (Q) 4- RLINK (Р), RTAG(Q) <r- RTAG(P), RLINK(P) Q, RTAG(P) <- 0, LLINK(Q) P, LTAG(Q) <- 1.

12. [Является ли RLINK(P) нитью?] Если RTAG(Q) = О, установить LLINK(Q$) •(- Q. (Здесь Qs определяется алгоритмом S, который будет работать правильно, даже если LLINK (Q$) теперь указывает на узел NODE(P), а не на узел NODE(Q). Этот шаг необходим при вставке узла в середину прошитого дерева, а не при добавлении нового листа.)

Поменяв местами левую и правую стороны (например, обозначение Q$ заменяя обозначением JQ на шаге 12), получим аналогичный алгоритм для вставки узла слева.

До сих пор рассматривались бинарные деревья, в которых связи-нити проводились слева и справа. Однако существует еще одно важное представление, которое

занимает промежуточное положение между непрошитым и полностью прошитым представлениями. Так называемое правопрошитое бинарное дерево {right-threaded binary tree) представляет собой комбинацию этих двух подходов за счет использования правых связей-нитей RLINK, тогда как пустые левые поддеревья представлены связями-нитями LLINK = Л. (Аналогичным образом устроено левопрошитое бинарное дерево, но только в нем пустыми являются связи-нити LLINK.) В алгоритме S связи-нити LLINK практически не используются, поэтому, если заменить условие LTAG = О на шаге S2 условием LLINK / Л, получим алгоритм обхода правопрошитого бинарного дерева в симметричном порядке. Причем программа S может без каких-либо изменений работать с правопрошитыми бинарными деревьями. Для очень многих приложений бинарных древовидных структур требуется вьшолнять обход дерева только слева направо с помощью функций Ps и/или Р*, и потому для этих приложений нет необходимости прошивать связи-нити LLINK. Здесь рассмотрены случаи обхода в обоих направлениях (правом и левом) для того, чтобы указать на симметрию данной ситуации и ее возможности, но на практике прошивку гораздо чаще требуется вьшолнять только с одной стороны.

Рассмотрим теперь еще одно важное свойство бинарных деревьев и их связь с проблемой обхода узлов дерева. Говорят, что два бинарных дерева Т и Т подобны, если они имеют одинаковую структуру. Формально это значит, что либо (а) они оба пусты, либо (Ь) они оба не пусты, а их левое и правое поддеревья подобны соответственно. Иначе говоря, подобие означает, что схемы деревьев Т и Г имеют одинаковую "форму". Другими словами, подобие означает наличие взаимно однозначного соответствия между узлами деревьев Т и Г с сохранением структуры. Если узлы ui и U2 дерева Т соответствуют узлам ul и ы, дерева Г, то узел щ находится в левом поддереве U2 тогда и только тогда, когда узел и[ находится в левом поддереве uj. Это утверждение верно и для правых поддеревьев.

Бинарные деревья Т и Т называются эквивалентными {equivalent), если они подобны и соответствующие узлы содержат одинаковую информацию. Формально пусть info(u) обозначает информацию, которая содержится в узле и; в таком случае деревья эквивалентны тогда и только тогда, когда либо (а) они оба пусты, либо (Ь) они оба не пусты и info (корень(Т)) = 1пГо(корень(Г)), а их левые и правые поддеревья соответственно эквивалентны.

В качестве примера этих определений рассмотрим следующие четыре бинарных дерева:

Первые два из ннх не являются подобными. Второе, третье и четвертое - подобны, а второе и четвертое - эквивалентны.

В некоторых приложениях, использующих древовидные структуры, необходимо определить подобие или эквивалентность бинарных деревьев. Для этого полезно рассмотреть след>-ющ}Ю теорему.