Произвольное fc

fc = 2

fc = 1

fc = 0

Рис. 24. Общая ориентация левых и правых связей-нитей в прошитом бинарном дереве. Волнистые линии обозначают связи с другими частями дерева (или ведущие к ним нити).

Согласно этому определению каждая новая связь-нить указывает непосредственно на узел-предшественник или узел-последователь конкретного узла в заданном симметричном порядке. На рис. 24 показана общая ориентация связей-нитей в любом бинарном дереве.

В некоторых алгоритмах гарантируется, что корень любого поддерева всегда располагается в ячейках памяти, которые находятся в памяти ниже других узлов этого поддерева. В тако.м случае LTAG(P) будет равно 1 тогда и только тогда, когда LLINK (?) < Р, поэтому поле LTAG, как и поле RTAG, будет содержать избыточную информацию.

Значительным преимуществом прошитых деревьев является то, что алгоритмы обхода для них существенно упрощаются. Например, с помощью приведенного ниже алгоритма можно вычислить Р$ по заданному значению Р.

Алгоритм S {Симметричный (центрированный) узел-последователь в прошитом бинарном дереве). Если Р указывает на узел прошитого бинарного дерева, то данный алгоритм устанавливает Q 4- Р$.

51. [RLINK(P) -это нить?] Установить Q 4- RLINK(P). Если RTAG(P) = 1, прекратить выполнение алгоритма.

52. [Поиск слева.] Если LTAG(Q) = О, установить Q <- LLINK(Q) и повторить этот шаг. В противном случае прекратить выполнение алгоритма.

Обратите внимание на то, что для его выполнения не потребуется стек, который применялся в алгоритме Т. Действительно, с помощью обычного представления (2) невозможно найти Ps столь%;ясе эффективным путем, знгья только адрес Р произвольно выбранного узла дерева. Поскольку в обычном представлении бинарного дерева нет направленных вверх связей, то нет и сведений о том, какие узлы расположены выше, если только не сохранять информацию о пути к данному узлу. Стек в алгоритме Т используется как раз для хранения этой информации при отсутствии нитей.

Алгоритм S назван эффективным, хотя это свойство не всегда очевидно, поскольку шаг S2 может выполняться достаточно много раз.. Может быть, вместо многократного повторения шага S2 для ускорения процесса следовало бы использовать стек, как в алгоритме Т? Для исследования этого вопроса выясним, сколько раз в среднем выполнялся шаг S2, если Р указывает "произвольный" узел дерева, или, что то же самое, определим общее количество выполнений шага S2, если алгоритм S повторно используется для обхода всего дерева.

Выполняя этот анализ, полезно будет также познакомиться с программами, в которых реализованы алгоритмы S и Т. Как обычно, при разработке алгоритмов следует учесть возможность их применения для пустых бинарных деревьев, и, если Т является указателем данного дерева, желательно, чтобы LOC(T)* и LOC(T)s были первыми узлами в прямом и симметричном порядках соответственно. Для прошитых деревьев узел NODE(LOC(T)) удобно преобразовать в "заголовок списка" для дерева со следующими параметрами:

LLINK(HEAD) = Т, LTAG(HEAD) = О,

RLINK (HEAD) = HEAD, RTAG (HEAD) = 0.

(Здесь HEAD обозначает LOC(T), т. e. адрес заголовка списка.) Пустое прошитое дерево удовлетворяет условиям

LLINK(HEAD) = HEAD, LTAG(HEAD) = 1.

Дерево растет за счет вставки узлов слева от заголовка списка. (Эти начальные условия преимущественно продиктованы алгоритмом вычисления Р*, который рассматривается в упр. 17.) В соответствии с этими соглашениями прошитое представление бинарного дерева (1) для компьютера будет выглядеть так:

Заголовок списка

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

В непрошитом дереве LTAG и RTAG всегда будут равны "-Ь", а концевые связи будут представлены нулем. В прошитом дереве знак "-Ь" используется для меток, которые равны О, а знак "-"-для меток, которые равны 1. Обозначения LLINKT и RLINKT будут использоваться для полей LTAG-LLINK и RTAG-RLINK соответственно.

Два бита метки занимают знаковые ячейки слова в памяти компьютера MIX, которые ни для чего другого все равно не используются, а потому они не занимают лишнего места в памяти. Аналогично в компьютере MMIX можно было бы "бесплатно" использовать младшие биты полей связи в качестве битов метки, поскольку указатель обычно принимает четные значения, а также потому что при адресации памяти в компьютере MMIX проще игнорировать именно младшие биты.

В следующих двух программах выполняется обход бинарного дерева в симметричном (т. е. центрированном) порядке с периодическими переходами к ячейке VISIT, в то время как индексный регистр 5 указывает на текущий узел.

Программа Т. В этой реализации алгоритма Т стек находится в ячейках А -Ь 1, А 4- 2, ..., А-Ь МАХ; г1б является указателем стека и г15 = Р. Событие переполнения (OVERFLOW) происходит при недопустимом возрастании размеров стека. Эта программа незначительно отличается от алгоритма Т (шаг Т2 в нем встречается трижды), поэтому не нужно проверять, пуст ли стек, при переходе от шага ТЗ к шагу Т2, а затем - к шагу Т4.