Общее время выполнения равно 21п+6а -3-146, где п - количество узлов, а - количество пустых связей RLINK (следовательно, а - 1-это количество непустых связей LLINK), 6 - количество узлов на "правом хребте" дерева Т, RLINK (Т), RLINK (RLINK (Т)) и т. д.

23. Вставка узла справа: RLINKT(Q) +- RLINKT (Р), RLINK(Р) -f- Q, RTAG(P) (- О, LLINK (Q) <r- Л. При вставке узла слева при условии, что LLINK (Р) = Л, нужно выполнить следующие действия: установить LLINK (Р) +- Q, LLINK (Q) Л, RLINK (Q) •(- Р, RTAG(Q) +- 1. Вставка узла слева между Р и LLINK(Р) ф Л: установить R LLINK(Р), LLINK(Q) +- R, а затем не устанавливать или устанавливать R RLINK (R) до тех пор, пока не выполнится условие RTAG(R) = 1; и наконец, установить RLINK (R) -f- Q, LLINK(Р) +- Q, RLINK (Q) P, RTAG(Q) +- 1.

(B последнем случае можно использовать более эффективный алгоритм, если известен такой узел F, что Р = LLINK(F) или Р = RLINK (F). Например, если предположить, что выполняется последнее из этих двух равенств, можно установить INFO(P) О INFO(Q), RLINK (F) •(- Q, LLINK(Q) +- P, RLINK (P) -f- Q, RTAG(P) 1. Хотя для выполнения этих действий потребуется фиксированное время, в общем случае их не рекомендуется использовать, поскольку при этом повсюду в памяти компьютера придется выполнять интенсивный обмен содержимым узлов.)

24. Нет, как видно из этого примера.

25. Сначала методом индукции по количеству узлов дерева Т докажем (Ь), а затем аналогично- (с). Для доказательства (а) рассмотрим несколько случаев Обозначим Т-<i Г, если выполняется условие (i), обозначим Г Хг Г, если выполняется условие (li), и т. д. Тогда из Г Xl Г и Т X Г" следует Г Xi Г"; Г Хг Г и из Г X Г" следует Г Xj Г"; оставшиеся два случая доказываются методом индукции по количеству узлов в дереве Т.

26. Если в результате двойного порядка обхода дерева Г получена последовательность (ui,di), (U2,d2),..., (U2„,d2n), где и - это узлы и dk равны 1 или 2, построим "след" дерева {v\, Si), {v2, sz), , {v2n, S2n), где Vj = info(Uj), a. Sj = l{uj) или r(uj) в зависимости от того, dj - I или dj = 2 соответртвенно. Теперь Т -< Т тогда и только тогда, когда определенный выше след дерева Т лексикографически предшествует или равен следу дерева Г. Формально это значит, что либо п < п к. [vj, s,,) = [vj, sj) для 1 < J < n, либо есть такое к,

для которого (Vj ,Sj) = {Vj,sj) для 1 < J < А: и либо Vk X Ij., либо Vk = vl, и < s.-

27. RI. [Инициализация ] Установить P +- HEAD, P <- HEAD; это заголовки соответствую-

щих списков данных правопрошитых бинарных деревьев. Перейти к шагу R3.

R2. [Проверка поля INFO.] Если INFO(P) X INFO(P), прекратить выполнение алгоритма (Г X Т); если INFO(P) >- INFO(P), прекратить выполнение алгоритма (Г у Г).

КЗ. [Переход влево] Если LLINK(Р) = Л = LLINK(Р), перейти к шагу R4; если LLINK (Р) = Л / LLINK (Р), прекратить выполнение алгоритма (Г X Т), если LLINK(Р) / Л = LLINK(Р), прекратить выполнение алгоритма (Г >- Т); в противном случае установить Р LLINK(Р), Р LLINK(Р) и перейти к шагу R2.

R4. [Конец обхода] Если Р = HEAD (или, что эквивалентно, если Р = HEAD), прекратить выполнение алгоритма (Т эквивалентно Г).

R5. [Переход вправо.] Если RTAG(P) = 1 = RTAG(P), установить Р <- RLINK (Р), Р <- RLINK (Р) и перейти к шагу R4. Если RTAG(P) = 1 # RTAG(P), прекратить выполнение алгоритма (Т ч Т). Если RTAG(P) # 1 = RTAG(P), прекратить выполнение алгоритма (Т >- Т). В противном случае установить Р «- RLINK(Р), Р 4- RLINK(Р) и перейти к шагу R2.

Для доказательства справедливости этого алгоритма (и, следовательно, для понимания принципа его работы) можно методом индукции по размеру дерева То показать, что справедливй следуюш;ее утверждение: "Начиная с шага R2 с Р и Р, указывающими на корни двух непустых правопрошитых бинарных деревьев То и То, выполнение алгоритма прекращается, если То и То не эквивалентны, но известно, что либо То -< То, либо То >- Tq. Алгоритм достигнет шага R4, если То и То являются эквивешентными с Р и Р, указывающими соответственно на узлы-последователи для узлов То и То в симметричном порядке".

28. Исходное дерево эквивалентно и подобно его копии.

29. Докажите методом индукции по размеру дерева Т, что справедливо следующее утверждение: "Начиная с шага С2 с Р, указывающим на корень непустого бинарного дерева Т, с Q, указывающим на узел, который имеет пустые левое и правое поддеревья, эта процедура в конечном итоге достигнет шага Сб после установки INFO(Q) <- INFO(P) и присоединения копий левого и правого поддеревьев узла NODE(P) к узлу NODE(Q) и с Р и Q, указывающими соответственно на узлы-предшественники деревьев Т и узла NODE(Q) в прямом порядке".

30. Предположим, что указатель Т в (2) равен LLINK (HEAD) в (10). Ll. [Инициализация.] Установить Q <- HEAD, RLINK(Q) <- Q. L2. [Продвижение.] Установить Р <- Q$ (см. ниже).

L3. [Прошивка.] Если RLINK(Q) = Л, установить RLINK(Q) 4- Р, RTAG(Q) <- 1; в противном случае установить RTAG (Q) 4-0. EcnHLLINK(P) = Л, установить LLINK(Р) +-Q, LTAG(P) 1; в противном случае установить LTAG(P) 0.

L4. [Обход завершен?] Если Р ф HEAD, установить Q <- Р и вернуться к шагу L2.

На шаге L2 этого алгоритма предполагается активизация сопрограммы симметричного порядка обхода, как в алгоритме Т, с дополнительным условием, что алгоритм Т посещает узел HEAD после полного обхода всего дерева. Это обозначение является удобным упрощением при описании алгоритмов обхода деревьев, поскольку не требуется повторять описание стека из алгоритма Т. Конечно, на шаге L2 не может использоваться алгоритм S, поскольку дерево еще не прошито. Но алгоритм из упр. 21 использовать можно, и благодаря этому появляется еще один удобный метод прошивки дерева без какого-либо вспомогательного стека.

31. XI. Установить HEAD.

Х2. Установить Q <- Р$ (используя, например, алгоритм S модифицированного правопрошитого дерева).

ХЗ. Если Р # HEAD, установить AVAIL <= Р.

Х4. Если Q Ф HEAD, установить Р ч- Q и вернуться к шагу Х2.

Х5. Установить LLINK(HEAD) 4- Л.

Очевидно, что возможны и другие решения, которые сокращают протяженность внутреннего цикла, хотя порядок основных шагов довольно сомнителен. Указанная процедура работоспособна, поскольку ни один узел не возвращается в область доступных ячеек до тех пор, пока алгоритм S не исслед>ет его связи LLINK и RLIM. Как упоминалось в тексте данного раздела, каждая из этих связей используется в точности один раз при полном обходе дерева.

32. RLINK (Q) 4-RLINK (Р), SUC(Q) 4-SUC(P), SUC(P) 4-RLINK(P) 4-Q, PRED(Q) 4-P, PRED (SUC (Q)) 4- Q.

33. Вставка узла NODE(Q) слева и снизу узла NODE(P) выполняется довольно просто: установить LLINKT(Q) 4- LLINKT(P), LLINK(P) 4- Q, LTAG(P) 4- 0, RLINK(Q) 4- Л. Вставку справа выполнить гораздо сложнее, поскольку для этого необходимо найти *Q, что так же сложно выполнить, как и найти Qtl (см. упр. 19). Для этого можно использовать метод перемещения узлов, который рассматривается в упр. 23. Поэтому в общем случае вставки при таком типе прошивки выполняются гораздо сложнее. Но вставки согласно алгоритму С выполняются гораздо проще, чем вставки общего типа. Действительно, процесс копирования осуществляется несколько быстрее для такого типа прошивки.

С1. Установить Р 4- HEAD, Q 4- U, перейти к шагу С4. (Далее используются предположения и идеология алгоритма С из данного раздела.)

С2. Если RLINK(P) ф Л, установить R < AVAIL, LLINK(R) 4- LLINK(Q), LTAG(R) 4- 1, RLINK (R) 4- Л, RLINK(Q) 4- LLINK (Q) 4- R.

C3. Установить INFO(Q) 4- INFO(P).

C4. Если LTAG(P) = 0, установить R AVAIL, LLINK(R) 4- LLINK(Q), LTAG(R) 4- 1, RLINK(R) 4- Л, LLINK(Q) 4- R, LTAG(Q) 4- 0.

Cb. Установить P 4- LLINK(P), Q 4- LLINK(Q).

C6. Если P Ф HEAD, перейти к шагу C2.

Теперь этот алгоритм выглядит настолько простым, что возникают сомнения в его корректности!

Алгоритм С для прошитых или правопрошитых бинарных деревьев выполняется несколько дольше из-за дополнительных затрат времени на вычисление Р*, Q* на шаге С5.

Можно обычным образом прошить связи RLINK или поместить вР в RLINK (Р) в сочетании с методом копирования за счет заданных соответствующим образом значений RLINK (R) и RLIMT(Q) на шагах С2 и С4.

34. А1. Установить Q 4- Р, а затем ни разу не устанавливать или устанавливать Q 4-

RLIM(Q) до тех пор, пока не выполнится условие RTAG(Q) = 1.

А2. Установить R 4- RLINK(Q). Если LLINK(R) = Р, установить LLIM(R) 4- Л. В противном случае установить R 4- LLINK (R), затем ни разу не устанавливать или устанавливать R 4- RLINK(R) до тех пор, пока не выполнится условие RLINK (R) = Р; наконец, установить.RLIMT(R) 4- RLINKT(Q). (На этом шаге узел NODE(P) и его поддеревья удаляются из исходного дерева.)

A3. Установить RLINK(Q) 4- HEAD, LLIM(HEAD) 4- P.

(Ключом к успеху при разработке и/или понимании этого алгоритма является построение достаточно наглядных схем состояний "до и после".)

36. Нет; см. ответ к упр. 1.2.1-15(е).

37. EcлиLLIЖ(P) = RLIM(P) = Л для представления (2), положим LIM(Р) = Л; в противном случае положим LINK(P) = Q, где NODE(Q) соответствует NODE (LLINK (Р)) и N0DE(Q+1) соответствует NODE (RLINK (Р)). Условие LLIM(P) или RLIM(P) = Л представлено с помощью признака в узле NODE(Q) и.пи N0DE(Q+1) соответственно. Для этого представления потребуется от п до 2п - 1 ячеек памяти. Для принятых допущений в случае (2) потребовалось бы 18 слов памяти по сравнению с 11 словами в данной схеме. При этом операции вставки и удаления будут выполняться приблизительно с одинаковой эффективностью в любом представлении. Но данное представление не так универсально при совместной работе с другими структурами.