► 10. [20] Какое максимальное количество элементов может находиться в стеке во время выполнения алгоритма Т при работе с деревом с п узлами? (Ответ на этот вопрос очень важен при распределении памяти, когда стек располагается в последовательных ячейках памяти.)

11. [HM4I] Найдите среднее значение для наибольшего размера стека при выполнении алгоритма Т в зависимости от числа узлов п при условии, что все бинарные деревья с п узлами рассматриваются как равновероятные.

12. [22] Напишите алгоритм, аналогичный алгоритму Т, который совершает обход бинарного дерева в прямом порядке, и докажите его корректность.

► 13. [24] Напишите алгоритм, аналогичный алгоритму Т, который совершает обход бинарного дерева в обратном порядке, и докажите его корректность.

14. [22] Покажите, что если бинарное дерево с п узлами имеет вид (2), то общее количество Л-связей в таком представлении можно выразить с помощью простой функции от п. Эта функция не зависит от формы дерева

15. [15] В прошитом представлении дерева (10) каждый узел, за исключением заголовка списка, имеет в точности одну связь, которая указывает на нее сверху вниз, а именно - связь от родителя этого узла. Некоторые узлы также имеют связи, которые указывают на них снизу вверх. Например, узел С имеет два указателя, направленных на него снизу вверх, а узел Е - только один** Существует ли простая зависимость между количеством связей, указывающих на данный узел, и другими основными свойствами узла? (Это нужно для того, чтобы при изменении структуры дерева знать количество связей, указывающих на узел.)

► 16. [22] Схемы, представленные на рис 24, позволяют предложить следующие интуитивно понятные правила расположения узла NODE(Q$) в бинарном дереве по отношению к узлу NODE(Q). Если узел NODE(Q) имеет непустое правое поддерево, рассмотрим Q = sP, Qs = Р в верхних схемах; узел NODE(Qs) является крайним слева узлом этого правого поддерева. Если узел NODE(Q) имеет пустое правое поддерево, рассмотрим Q = Р в нижних схемах. Наконец, чтобы определить положение узла NODE(Qs), следует перемещаться вверх по дереву до первой возможности перейти вправо

Предложите подобное "интуитивное" правило для поиска места расположения узла NODE(Q*) в бинарном дереве по отношению к узлу NODE(Q).

► 17. [22] Предложите алгоритм, аналогичный алгоритму S, для определения Р* в прошитом бинарном дереве. Предполагается, что дерево имеет заголовок списка, как в (8)-(10).

18. [24] Во многих алгоритмах работы с деревьями каждый узел может посещаться не один раз, а дважды за счет комбинации прямого и симметричного порядка, который называется двойным порядком{<1оиЫе order). Обход бинарного дерева в двойном порядке определяется так: если бинарное дерево пусто, ничего делать не надо. В противном случае необходимо

a) посетить корень (первый раз);

b) пройти левое поддерево в двойном порядке;

c) посетить корень (во второй раз);

d) пройти правое поддерево в двойном порядке.

Например, после обхода дерева (1) в двойном порядке получим последовательность

AiBiDiD2B2A2CiEiE2GiG2C2FiHiH2F2JiJ2,

где А\ означает, что А посещается впервые.

Если Р указывает на узел дерева и d = 1 или 2, положим (P,d) = (Q,e), если следующи.м шагом в двойном порядке после посещения узла NODE(P) в d-й раз является

посещение узла NODE(Q) в е-й раз; или, если (Р,d) является последним шагом в двойном порядке, запишем (Р, d) = (HEAD, 2), где HEAD - это адрес заголовка списка. Предположим также, что (HEAD, 1) является первым шагом в двойном порядке.

Предложите алгоритм, аналогичный алгоритму S, для обхода бинарного дерева в двойном порядке, а также предложите алгоритм, аналогичный алгоритму S, для вычисления (P,d). Рассмотрите связь между этими алгоритмами и алгоритмами из упр. 12 и 17.

► 19. [27] Предложите алгоритм, аналогичный алгоритму S, для вычисления Pit (а) в пра-вопрошитом бинарном дереве; (Ь) в полностью прошитом бинарном дереве. Постарайтесь написать такой алгоритм, среднее время выполнения которого для произвольного узла дерева Р было бы мало, насколько возможно.

20. [23] Измените программу Т так, чтобы стек использовался в ней в виде связанного списка, а не в виде последовательно расположенных ячеек памяти.

► 21. [33] Создайте алгоритм обхода непрошитого бинарного дерева в симметричном порядке без использования вспомогательного стека. При Этом допускается произвольное изменение содержимого полей LLINK и RLINK в узлах дерева во время его обхода при условии, что данное бинарное дерево имеет обычное представление (2) как до, так и после выполнения алгоритма обхода. Причем в узлах дерева нельзя использовать никакие другие биты.

22. [25] Создайте программу для компьютера MIX для реализации алгоритма из упр. 21 и сравните время ее выполнения со временем выполнения программ S и Т.

23. [22] Предложите алгоритм, аналогичный алгоритму I, для вставки узла справа и слева в правопрошитом бинарном дереве. Предположим, что узлы содержат поля LLINK, RLINK и RTAG.

24. [М20] Будет ли справедлива теорема А, если узлы деревьев Т и Т располагаются не в прямом, а в симметричном порядке?

25. [М24] Пусть Т-множество бинарных деревьев, S - множество полей info, которые содержатся в узлах этих деревьев, причем S является линейно упорядоченным на основе отношения :< (см. упр. 2.2.3-14). Определим отношение Т< Т для любых деревьев Ти Г из множества Т тогда и только тогда, когда

i) Т пусто; либо

ii) Т и Т не пусты и info(root(r)) -< info(root(r)); либо

iii) Т и Г не пусты, info(root(r)) = info(root(r)), left(r) :< left(r) и 1еЛ(Г) не эквивалентно left (Г);, либо

iv) Т и Т не пусты, info(root(T)) = info(root(r)), left(T) эквивалентно left(r) и riglit(r) < right(r).

Здесь left(r) и right(r) обозначают соответственно левое и правое поддеревья дерева Г, а root (Г) -корень дерева Т. Докажите, что (а) из Т Т и Т : Г" следует Г ;< Г"; (Ь) Г эквивалентно Г тогда и только тогда, когда Т-<Т иТ < Г; (с) для любого Г, Г из множества Т имеет место либо Т-<Т, либо Т < Т. [Таким образом, если эквивалентные деревья множества Т рассматриваются как равные, то отношение порождает линейное упорядочение множества Т. Это упорядочение имеет много приложений (например, для упрощения алгебраических выражений). Если S содержит только один элемент, т. е. поля info всех элементов одинаковы, имеет место особый случай, когда Эквивалентность равносильна подобию.]

26. [М24] Рассмотрим упорядочение Т < Г, определенное в предыдущем упражнении. Докажите теорему, аналогичную теореме А, которая дает необходимое и достаточное условие, что Г; Т, а также использует понятие двойного порядка обхода, которое определено в упр. 18.

► 27. [28] Предложите алгоритм для проверки отношения двух деревьев Т и Т (либо Г -< Г, либо Г >- Г, либо Г эквивалентно Г) на основании отношения, определенного в упр. 25, предполагая, что обабинарных дерева являются правопрошитыми. Предположим, что каждый узел имеет поля LLINK, RLINK, RTAG, INFO, a вспомогательный стек не используется.

28. [00] Копия бинарного дерева, полученного с помощью алгоритма С, будет эквивалентна исходному дереву или подобна ему?

29. [М25] Предложите наиболее строгое доказательство справедливости алгоритма С.

► 30. [22] Предложите алгоритм прошивки непрошитого дерева, который, например, преобразует (2) в (10). Замечание. По возможности используйте обозначения типа Р* и Ps вместо повторения шагов алгоритмов обхода наподобие алгоритма Т.

31. [23] Предложите алгоритм, который "стирает" правопрошитое бинарное дерево. Он должен возвратить все узлы дерева, за исключением заголовка списка, в список свободных ячеек AVAIL, причем заголовок списка отвечает пустому бинарному дереву. Предположим, что узел имеет поля LLINK, RLINK, RTAG, а вспомогательный стек не используется.

32. [21] Предположим, что каждый узел бинарного дерева имеет четыре поля связи: LLINK и RLINK, которые указывают на левое и правое поддеревья или Л, как и в непрошитом дереве, а также SUC и PRED, которые указывают на предшественника и последователя узла в симметричном порядке. (Значит, SUC(P) = Ps и PRED(P) = sP. Такое дерево содержит больше информации, чем прошитое дерево.) Создайте алгоритм, подобный алгоритму I, для вставки в такое дерево.

► 33. [30] Существует более одного способа прошивки дерева! Рассмотрим следующее представление, используя три поля LTAG, LLINK, RLINK в каждом узле:

LTAG(P): определяется так же, как и в прошитом бинарном дереве; LLINK(Р): всегда равно Р*;

RLINK(Р): определяется так же, как и в непрошитом бинарном дереве.

Обсудите алгоритмы вставки для такого представления и предложите для данного представления алгоритм копирования (т. е. алгоритм С) с подробным описанием.

34. [22] Пусть Р указывает на узел в некотором бинарном дереве, а HEAD - на заголовок списка в пустом бинарном дереве. Предложите алгоритм, который (i) удаляет узел NODE(P) и все его поддеревья из любого дерева, а также (ii) присоединяет узел NODE (Р) и его поддерево к NODE (HEAD). Предположим, что все рассматриваемые бинарные деревья прошиты справа с полями LLINK, RTAG, RLINK в каждом узле.

35. [40] Дайте определение тройного depeea(temary tree) (а в более общем случае - t-арного дерева для произвольного t > 2), аналогичное определению бинарного дерева, и исследуйте возможность обобщения для <-арных деревьев результатов, полученных в этом разделе и в упражнениях после него.

36. [М23] В упр. 1.2.1-15 показано, что лексикографический порядок расширяет полное упорядочение множества S до полного упорядочения множеств из п элементов множества S. В приведенном выше упр. 25 показано, что линейное упорядочение данных в узлах дерева может быть расширено до линейного упорядочения деревьев на основе аналогичного определения. Если отношение -< приводит к полному упорядочению множества S, то является ли расширенное отношение из упр. 25 полным упорядочением набора Т?

► 37. [24] (Задача Д. Фергюсона.) Если два слова в памяти компьютера обязательно должны содержать два поля связи и поле INFO с данными, то в таком случае для представления дерева типа (2) с п узлами потребуется 2п слов. Создайте схему представления бинарных