Q +- RLINK(Q) до тех пор, рока не будет соблюдено условие RTAG(Q) = 0. Наконец, еще один раз установить Q <- RLINK (Q).

18. Измените алгоритм Т, вставив следующий шаг Т2.5: "Попасть в узел NODE(P) (в первый раз)", а на шаге Т5 узел NODE(P) будет посещен уже во второй раз.

Обход прошитого дерева выполняется очень просто:

(Р, 1)" = (LLINK(Р), 1), если LTAG(P) = О, в противном стучае (Р,2); (Р,2) = (RLINK(Р), 1), если RTAG(P) = О, в противном случае (RLINK(Р),2). В любом случае в дереве происходит переход только на один шаг, поэтому на самом деле двойной порядок и значения d и е включаются в программу без явного упоминания.

Опуская все посещения узлов в первый раз, получим в точности алгоритмы Т и S, а опуская все посещения узлов во второй раз, получим решения упр. 12 и 17.

19. Основная идея заключается в поиске родителя Q узла Р. Если Р ф LLINK (Q), то получим РК = Q; в противном случае получим Р«, повторно устанавливая Q +- Q$ несколько раз (может быть, это вовсе не потребуется делать) до тех пор, пока не выполнится условие RTAG (Q) =1. (См., например, Р и Р« в показанном ниже дереве.)

Для общего случая правопрошитого дерева не существует эффективного алгоритма поиска родителя узла Р, так как вырожденное правопрошитое дерево, в котором все левые связи пусты, является циклическим списком, в котором связи проведены в другом направлении. Следовательно, нельзя совершить обход правопрошитого дерева в обратном порядке с такой же эффективностью, как при использовании стека в упр. 13, без сохранения информации о пути к текущему узлу Р.

Но если дерево прошито в обоих направлениях, родителя узла Р можно найти следующим достаточно эффективным способом.

F1. Установить Q •<- Р и R •<- Р.

F2. Если LTAG(Q) = RTAG(R) = О, установить Q +- LLINK (Q) и R •<- RLINK(R) и повторить этот шаг. В противном случае перейти к шагу F4, если RTAG(R) = 1.

F3. Установить Q +- LLINK(Q) и прекратить выполнение алгоритма, если Р = RLINK(Q). В противном случае не устанавливать или устанавливать R ч- RLINK (R) до тех пор, пока не выполнится условие RTAG(R) = 1; затем установить Q <- RLINK (R) и прекратить выполнение алгоритма.

F4. Установить R •<- RLINK (R) и прекратить выполнение алгоритма с Q 4- R, если Р = LLINK (R) В противном случае не устанавливать или устанавливать Q •(- LLINK (Q) до тех пор, пока не выполнится условие LTAG(Q) = 1; затем установить Q <- LLINK (Q) и прекратить выполнение алгоритма.

Среднее время выполнения алгоритма F для произвольного узла Р дерева равно 0(1). Действительно, если подсчитать только шаги Q •(- LLINK (Q), когда Р - правый потомок.

или только шаги R <- RLINK (R) когда Р - левый потомок, то обход каждой связи будет выполнен в точности для одного узла Р.

20. Строки 06-09 нужно Строки 12 и 13 нужно заменить строками заменить строками

ТЗ ENT4 0,6 LD4 О,6(LINK)

LD6 AVAIL LD5 0,6(INFD)

J6Z OVERFLOW LDX AVAIL

LDX 0,6(LINK) STX 0,6(LINK)

STX AVAIL ST6 AVAIL

ST5 0,6(INFO) ENT6 0.4

ST4 0,6(LINK)

Если в строку 06 добавить еще две строки

ТЗ LD3 О,5(LLINK)

J3Z Т5 Перейти к шагу Т5, если LLINK (Р) = Л.

с соответствующими изменениями строк 10 и И, то время выполнения программы (ЗОп + а + 4)и сократится до (27а + 6п - 22)и. (Аналогично можно было сократить время выполнения программы Т до (12а + 6п - 7)и, что несколько меньше при а = (п + 1)/2.)

21. Приведенное ниже решение Джозефа М. Морриса [Joseph М. Morris, Inf. Proc. Letters 9 (1979), 197-200] позволяет совершить обход только в прямом порядке (см. упр. 18).

U1. [Инициализация.] Установить Р +- Т и R +- Л.

U2. [Обход завершен?] Если Р = Л, прекратить выполнение алгоритма.

из. [Обход слева.] Установить Q 4- LLINK(Р). Если Q = Л, посетить узел NDDE(P) в прямом порядке и перейти к шагу U6.

U4. [Поиск связи-нити.] Ни разу не устанавливать или устанавливать Q +- RLINK (Q) до тех пор, пока не выполнится либо условие Q = R, либо условие RLINK(Q) = Л.

U5. [Вставка или удаление связи-нити.] Если Q ф Л, установить RLINK(Q) •<- Р и перейти к шагу U8. В противном случае установить RLINK(Q) •(- Л (связь-нить временно была установлена в Р, а теперь совершим обход левого поддерева Р).

U6. [Посещение в симметричном порядке.] Посетить NDDE(P) в симметричном порядке.

U7. [Переход вверх или вправо.] Установить R •(- Р, Р •<- RLINK (Р) и вернуться к шагу U2.

U8. [Посещение в прямом порядке.] Посетить NDDE(P) в прямом порядке.

U9. [Переход влево.] Установить Р •(- LLINK (Р) и вернуться к шагу U3.

Моррис также предложил несколько более сложный способ обхода дерева в обратном порядке.

Совершенно иное решение было найдено Дж. М. Робсоном [J. М. Robson, Inf. Proc. Letters 2 (1973), 12-14]. Назовем узел заполненным, если его связи LLINK и RLINK не пусты, и назовем его пустым, если обе его связи LLINK и RLINK пусты. Робсон нашел способ организации стека указателей на заполненные узлы, правые поддеревья которых посещаются во время обхода дерева, используя поля связи из пустых узлов!

Еще один способ избежать использования вспомогательного стека был независимо найден Г. Э. Линдстромом и Б. Двайером [G. Lindstrom and В. Dwyer, Jnf. Proc. Letters 2 (1973), 47-51, 143-145]. В их алгоритме обход дерева совершается в тройном порядке (triple order), т. е. каждый узел посещается в точности три раза: один раз - в прямом.

второй - в симметричном, а третий - в обратном порядке. Но при этом неизвестно, какой из порядков задействован для посещения узла в текущий момент.

W1. [Инициализация.] Установить Р +- Т и Q -f- S, где S - это значение метки, т. е. любое число, которое наверняка отличается от значения любой другой связи в данном дереве (например, -1).

W2. [Пропуск пустой связи.] Если Р = Л, установить Р Q и Q Л.

W3. [Обход завершен?] Если Р = S, прекратить выполнение алгоритма. (По завершении работы алгоритма получим Q = Т.)

W4. [Посещение узла.] Попасть в узел NODE(P).

W5. [Обращение.] Установить R +- LLINK(P), LLINK(P) +- RLINKCP), RLINK(Р) +- Q, Q +- P, P +- R и вернуться к шагу W2.

Справедливость алгоритма следует из того, что если начать шаг W2 со значением Р, указывающим на корень бинарного дерева Т, и значением Q, указывающим на X, где X не является связью в этом дереве, то данный алгоритм трижды выполнит обход дерева и достигнет Ш(1га W3 со значениями Р = X и Q = Т.

Если q(T) = Х1Х2 хзп является результирующей последовательностью узлов в тройном порядке обхода, то в таком случае получим а(Т) = Ta(LLINK(T)) Т q(RLINK(T) ) Т. Следовательно, как и заметил Линдстром, три подпоследовательности Х1Х4.. хзп-2, Х2Х5 ... хз„-1, хзхе ... хзп содержат все узлы дерева, причем каждый из них встречается в них всего один раз. (Так как узел Xj+i является либо родителем, либо потомком узла Xj, эти подпоследовательности посещают узлы таким образом, что каждый из них находится на расстоянии не более трех связей от своего предшественника. В разделе 7.2.1 описывается общая схема обхода, которая называется прямообратным порядком (prepostorder) и обладает этим свойством не только в отношении бинарных деревьев, но и деревьев общего типа.)

22. В этой программе применяются обозначения и соглашения, используемые в программах Т и S, с Q в регистре г16 и/или г14. Старомодный компьютер MIX не очень подходит для сравнения индексных регистров, поэтому переменная R опущена и проверка условия Q = R заменена проверкой условия RLINK (Q) = Р.