21. 1 + О rai + 1 п2 + • • • + (яз - 1) • Пт- Доказательство. Количество узлов в дереве равно

Яо + п1 + п2 Ч----+ Пт, и оно также равно 1 + (количество детей в дереве) = 1 + О • по +

1 Ш + 2 • гаг Ч-----h m • Пт.

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

Это можно реализовать несколькими способами. Например, один из них заключается в представлении корня с помощью линии, проведенной от центра страницы в альбомной ориентации к ее верхнему краю. Причем представление левого поддерева получится в левой половине страницы после поворота на 90° по часовой стрелке, а правого поддерева - в правой половине страницы после поворота на 90° против часовой стрелки. Затем каждый узел будет представлен линией половинной длины (по сравнению с длиной предыдущего отрезка), проведенной снизу вверх. (Если применить этот метод для полного бинарного дерева (complete binary tree) с 2* - 1 узлами на к уровнях, получатся так называемые Н-деревья (H-trees), которые представляют наиболее эффективную компоновку таких бинарных деревьев на СБИС-микросхеме (VLSI chip) (см. R. Р. Brent and И. Т. Kung, Inf. Proc. Letters 11 (1980), 46-48.)

H F J

E G

Другой способ заключается в представлении пустого бинарного дерева в виде прямоугольника и в таком вращении представления для поддеревьев непустых бинарных деревьев, чтобы левые поддеревья располагались вперемешку слева или снизу от соответствующих правых поддеревьев в зависимости от четности очередного рекурсивного шага этого построения. В результате подобного построения прямоугольники будут соответствовать внешним узлам расширенного бинарного дерева (см. раздел 2.3.4.5). Это представление, в значительной степени связанное с понятиями 2-мерных (2-d trees) и четырехмерных (quadtrees) деревьев, которое обсужд£1ется в разделе 6.5, особенно удобно использовать, когда информацию содержат внешние, а не внутренние узлы.

РАЗДЕЛ 2.3.1

1. INFD(T) = А, INFO (RLINK (Т)) = С и т. д.; в результате получим Я.

2. В прямом порядке обхода: 1245367; в симметричном порядке обхода: 4251637; в обратном порядке обхода: 4526731.

3. Да, справедливо. Обратите внимание, например в упр. 2, на то, что узлы 4-7 всегда располагаются в таком порядке. Этот результат можно получить автоматически методом индукции по раз.меру бинарного дерева.

4. Он является реверсивным по отношению к обратному порядку обхода. (Это легко можно доказать по индукции.)

5. Например, узлы дерева из упр. 2 в прямом порядке в двоичной системе (которая в данном случае эквивалентна десятичной системе обозначений Дьюи) выглядели бы так:

I, 10, 100, 101, 11, 110, 111. Здесь строки цифр рассортированы, как слова в словаре.

Вообще, при лексикографической сортировке слева направо узлы будут перечисляться в прямом порядке, если "пропуск" < О < 1, в обратном порядке, если О < 1 < "пропуск", и в симметричном порядке, если О < "пропуск" < 1.

(Более того, если представить пропуски слева и рассмотреть ярлыки в десятичной системе обозначений Дьюи как обычные числа в двоичной системе счисления, получим порядок уровней (level order); см. 2.3.3-(8).)

6. Тот факт, что последовательность piP2 Рп можно получить с помощью стека, легко доказывается методом индукции по п Действительно, нетрудно заметить, что именно эти действия выполняет стек в алгоритме Т (Соответствующая последовательность символов S и X, как в упр. 2.2.1-3, также соответствует последовательности цифр 1 и 2, которые используются в качестве индексов в двойном порядке; см. упр. 18.)

И наоборот, если последовательность рг • -Рп можно получить с помощью стека и если Рк = 1, то Pl .. .рк-1 является перестановкой {2,... ,к} и pit+i.. .р„ -перестановкой {к + 1,... ,п}. Эти перестановки соответствуют левому и правому поддеревьям, и их можно получить с помощью стека. Доказательство можно выполнить по индукции.

7. Используя прямой порядок, находим корень, а затем на основе симметричного порядка- левое и правое поддеревья Таким образом получим прямой и симметричный порядки этих поддеревьев. Следовательно, структуру такого дерева можно легко восстановить (действительно, создание простого алгоритма восстановления структуры дерева по узлам, связанным в прямом порядке связями-нитями LLINK и в симметричном порядке связями-нитями RLINK, представляет собой довольно интересную задачу). Аналогично можно восстановить структуру дерева, зная симметричный и обратный порядки. Но знания прямого и обратного порядков недостаточно для восстановления структуры любого дерева, поскольку существует два бинарных дерева, которые выглядят, как АВ, в прямом порядке и, как В А, в обратном порядке. Однако, если все неконцевые узлы бинарного дерева имеют по две непустые ветви, его структуру можно восстановить, зная прямой и обратный порядки

8. (а) Бинарные деревья со всеми пустыми связями LLINK. (b) Пустое бинарное дерево или дерево, содержащее только один узел (с) Бинарные деревья со всеми пустыми связями RLINK.

9. Tl выполняется один раз, Т2 - 2п+1 раз, ТЗ - п раз, Т4 - п+1 раз, Т5 - п раз. Эти значения можно получить либо методом индукции, либо с помощью закона Кирхгофа, либо непосредственно анализируя программу Т.

10. При обходе бинарного дерева со всеми пустыми связями RLINK потребуется поместить в стек адреса всех п узлов до того, как какие-либо из них будут удалены.

II. Пусть Ппк - количество бинарных деревьев с п узлами, для которых стек в алгоритме Т никогда не содержит более А: узлов. Если gk(z) - Zl„anA:;", то g\(z) = 1/(1 - z), g2(z) = 1/(1 - z/(l - z)) = (1 - z)/(l - 2z), ...,g,(z) = 1/(1 - zgk-i(z)) = qk-i(z)/qk(z), где q-i(z) = qo(z) = 1, qk+i(z) = qk(z) - zqk-i(z). Следовательно,

gk(z) = (h(z)+ - Mz)+)/(Mz)+ - Mz)"-),

где fj(z) = 1(1 ± vl - 4z). Теперь можно показать, что

а„, = К] (1 - и)(1 + и)(1 - и+)/(1 - и+).

Значит, s„ =53j,>j A:(a„A:-a«(A:-i)) равно (1+ w)" Ej>i "7(1) минус Onn-

Используя метод из упр. 5.2.2-52, получим асимптотический ряд

3 . И . -3/2.

W«.-. = 0- + i+O(n-/=).

[N. G. de Bruijn, D. E. Knuth, and S. O. Rice, in Graph Theory and Computing, ed. by R. C. Read (New York: Academic Press, 1972), 15-22.]

Если данное бинарное дерево представляет лес, описанный в разделе 2.3 2, то полученная величина является его высотой (height) (т. е. наибольшим расстоянием между корнем и узлами дерева плюс один). Обобщения этого результата для других вариантов деревьев были получены Флажоле и Одлыжко [J. Computer and System Sci. 25 (1982), 171-213]. Асимптотическое распределение высоты вблизи и вдали от среднего значения проанализированы Флажоле, Гао, Одлыжко и Ричмондом [Combinatorics, Probabiiitj, and Computing 2 (1993), 145-156].

12. Узел NDDE(P) следует посещать между шагами Т2 и ТЗ, а не между шагами Т4 и Т2. Чтобы доказать справедливость этого предложения, докажите истинность утверждения "Начиная с шага Т2 с ... исходным состоянием стека А, содержащим элементы А[1] ... А[т]" точно так, как в тексте данного раздела.

13. (Решение принадлежит С. Араухо (S. Araiijo), 1976 ) Оставим шаги Т1-Т4 без изменений, но сделаем так, чтобы Q инициализировалось значением Л на шаге Т1 и Q указывало на последний посещенный узел, если такой имеется. Шаг Т5 заменим двумя другими шагами.

Т5. [Правая ветвь пройдена?] Если RLINK(Р) = Л или RLINK(Р) = Q, перейти к шагу Т6; в противном случае установить А Р, Р RLINK(Р) и вернуться к шагу Т2.

Т6. [Попасть в Р.] Попасть в узел NODE(P), установить Q Р и вернуться к шагу Т4

Здесь применяется аналогичное доказательство. (Шаги Т4 и Т5 можно упростить таким образом, чтобы исключить операции извлечения узлов из стека с их немедленной повторной вставкой в стек.)

14. По методу индукции всегда существует в точности п -Ь 1 Л-связей (учитывая Т, когда эта связь пуста). Так как с учетом Т существует п непустых связей, замечание в данном разделе о преобладании пустых связей является справедливым.

15. Связь-нить LLINK или RLINK указывает на узел тогда и только тогда, когда он имеет непустое правое или левое поддерево соответственно (см. рис. 24).

16. Если LTAG(Q) = О, то Q*=LLINK(Q). Таким образом, узел Q* расположен на один шаг ниже и левее. В противном случае Q* можно найти, если пройти вверх по дереву (если это необходимо) повторно до первой возможности перейти вниз и вправо без вьтолнения повторных шагов. Типичными примерами таких проходов являются пути от Р к Р* и от Q к Q* в следующем дереве

17. Если LTAG(P) = О, установить Q <- LLINK (Р) и прекратить выполнение алгоритма. В противном случае установить Q +- Р, затем ни разу или несколько раз устанавливать