< Як-з{1 - + Як-2{1 - ls+2) + qk-sih+i - h+з) Н-----h Як-2{1к-4 - lk-2)

+ qk-i{lk-3 - I) + qkilk-2 - I)

(для нечетного к - s выводится похожее выражение). Отсюда следует, что 6 отрицательно, кроме случая 1к-2 = I-

41. EFGHTUXYZVWBCDAPQRJKLMINOSu-

42. Пусть qj = WT(Pj). Основная идея заключается в том, что на шагах С2-С6 все qk становятся большими, чем начальное значение qk-i + qk, или равными ему.

43. Вызвав рекурсивную процедуру mark{Pi,0), где тагк{Р,1) означает следующее:

LEVEL (Р) 4- I;

если LLINK(Р) ф Л, то шагА:(LLINK(Р)+ 1); если RLINK(P) ф А, то тагА:(RLINK(Р),« + 1).

44. Установите глобальные переменные t 4- О, m 4- 2п и вызовите рекурсивную подпрограмму build(l), где build(l) означает следующее.

Установить j <- т.

Если LEVEL (Х«) = /, то присвоить LLINK (Xj) +-t и t+-1 + I;

в противном случае присвоить т <- т - 1, LLINK (Xj) 4- Xm и build (I + 1). Если LEVEL (Х«) = I, то присвоить RLINK (Xj) +-1 и t <-t + I;

в противном случае присвоить m 4- m - 1, RLINK (Xj) 4- Xm и build(l + 1).

Переменная j локальна no отношению к построенной подпрограмме. (Это элегантное решение предложено Р. Е. Таржаном (R. Е. Tarjan), SICOMP 6 (1977), 639.) Вшгмание. Если числа lo, .., In не соответствуют никакому бинарному дереву, алгоритм зациклится.

45. Представить рабочий массив Ро, ..., Р« в виде списка с двойными связями, который также имеет связи со сбалансированным деревом (см. раздел 6.2.3). Если "попарно убывающие" веса равны до, ..., qt с qj в корне дерева, можно перейти по дереву влево или вправо на основании значений qj и qj+i; двойные связи обеспечивают мгновенный доступ к qj+i (Поля RANK не являются необходимыми; при чередовании сохраняется симметричный порядок, а потому вносить изменения в двойные связи не нужно.)

Отдельные семейства весов, для которых задача может быть решена за время 0(п), были представлены Ху (Ни) и Моргенталером (Morgenthaler) в Lecture Notes in Сотр. Sci. 1120 (1996), 234-243; однако неизвестно, достаточно ли времени 0(п) в общем случае.

46. См. IEEE Trans. С-23 (1974), 268-271; кроме того, см. упр. 6.2.3-21.

47. См. Altenkamp and Mehlhorn, JACM 27 (1980), 412-427.

48. He позволяйте сложному анализу случаев N = 3 (Jonassen and Knuth, J. Сотр. Syst. Sci. 16 (1978), 301-322) и Я = 4 (Baeza-Yates, BIT 29 (1989), 378-394) запугать вас! В этой области достигнут определенный прогресс (см. Louchard, Randrianarimanana, and Schott, Theor. Сотр. Sci. 93 (1992), 201-225).

49. Этот вопрос был впервые исследован Дж. М. Робсоном (J. М. Robson) (Australian Сотр. J. 11 (1979), 151-153), Б. Питтелем (В. Pittel) (J. JVfath. AnaJ. Applic. 103 (1984), 461-480) и Люком Девроем (Luc Devroye) (JACM 33 (1986), 489-498; Acta Inf. 24 (1987), 277-298), которые получили предельные формулы, выполняющиеся с вероятностью 1 при п -> оо; см. Н. М. Mahmoud, EvoJution of Random Search Trees (Wiley, 1992), гла-

ва 2. Впоследствии Люком Девроем и Брюсом Ридом (Bruce Reed) {SICOMP 24 (1995), 1157-1162) был найден попахивающий шаманством результат - они доказали, что средняя высота равна q In п + 0(log log п) с дисперсией 0(log log n), где

Q = 1/Г(1/2е) и 4.3110704070010050350470760964468902783916-,

а T{z) = 531 Ti"~z/n[ представляет собой функцию дерева.

РАЗДЕЛ 6.2.3

1. При преобразованиях должен сохраняться симметричный порядок узлов; в противном случае получить бинарное дерево поиска невозможно.

2. B(S) =0 только в том случае, когда S указывает на корень дерева (на шагах A3 и А4 значение S не изменялось) и все узлы от S до точки вставки сбалансированы.

3. Обозначим через ph наибольшее возможное отношение числа .несбалансированных узлов к общему количеству узлов в сбалансированном дереве высотой h. Тогда pi = О, Р2 = 5, рз = . Докажем, что р = (Pfe+i - l)/(Pfe+2 - 1). Пусть Th - дерево, которое максимизирует значение р; тогда можно предположить, что его левое поддерево имеет высоту h-1, а. правое - высоту h-2 (так как, если бы оба поддерева имели высоту h - l, интересующее нас отношение было бы меньше, чем ph-i)- Следовательно, это отношение для Th не превышает {ph-iNi + ph-iNr + l)/{Ni+Nr +1), где {Nt,Nr) - количество узлов в (левом, правом) поддереве. Приведенное выражение принимает максимальное значение при минимальных значениях {Ni, Nr). Значит, Th представляет собой дерево Фибоначчи и согласно упр. 1.2.8-28 р < - 1.

4. При h = 7 дерево

имеет большую длину пути. [Примечание. В работе С. С. Foster, Ргос. АСМ Nat. Conf. 20 (1965), 197-198, приведена некорректная процедура построения iV-узловых сбалансированных деревьев с максимальной длиной пути. Эдвард Логг (Edward Logg) обнаружил, что на рис. 3 у Фостера дан неоптимальный результат после 24 шагов (узел 22 может быть перемещен за узел 25).]

Дерево Фибоначчи порядка/i, однако, минимизирует значение (/i-ba)iV -(длина внешнего пути(Г)) по всем сбалансированным деревьям Т высотой /г-1 для любой неотрицательной константы а (это утверждение легко доказывается с помощью индукции по /г). Длина его внешнего пути равна hFh-i + (/i - l]Fh = {ф/Ъ)hFh+\ + 0{Fh+\) = @{Ь.ф). Следовательно, длина пути любого Л-узлового сбалансированного дерева не превышает

min(/iiV - ЩНф) + 0{N)) < iVlog N -N\ogф log N + 0{N).

Более того, если N велико и к = [\gN], h [к/\gф - \ogф к\ = log N - log log, N + 0(1), можно построить сбалансированное дерево с длиной пути hN+0{N) следующим образом: запишем Л-l-l = Fh+ Fh-i+ - + Fk+i +N = Fh+2 - Fk+2 + N и построим бинарное дерево с Л узлами; затем последовательно объединим его с деревьями Фибоначчи порядков к, к + 1, ...,h-l [см. R. Klein and D. Wood, Theoretical Сотр. Sci. 72 (1990), 251-264].

5. Это утверждение может быть доказано по индукции. Если Tn обозначает построенное дерево, имеем

при 2" < iV < 2" + 2"-1;

Гл. =

при2" + 2"- <Ж2"+.

Г2п 1 Tn-2"

6. Коэффициент при г" в zBj{z)Bk{z) представляет собой число бинарных деревьев с п узлами, левое поддерево которых сбалансировано и имеет высоту j, а сбалансированное правое поддерево имеет высоту к.

7. Сп+1 = Сп + 2Вп-\Вп-2\ следовательно, если положить qo = In2, qi = О, Qn+2 = ln(l + 2Bn+i5n/C+2) = 0{llBnCn+2) ив = exp(Qo/2 + Qi/4 + Q2/8 + - • •), TO можно найти,

что о < 2" - Сп = Cn(exp(Qn/2 + Qn+1 /4 + ...) 1) < 1, т. е. Cn = L2"J. Обобщение результатов для двойных экспоненциальных последовательностей приводится в Fibonacci Quarterly 11 (1973), 429-437. Выражение для в быстро сходится к значению

в = 1.43687 28483 94461 87580 04279 84335 54862 92481+.

8. Пусть bh = В;(1)/Вл(1) + 1 и пусть ен = 2BhBh-i{bh - bh-i)/Bh+i. Тогда bi = 2, bh+\ = 2bh - бл и бл = 0{bh/Bh-i); следовательно, bh = 2P + гн, где

/3 = 1 - б1 - б2 ----= 0.70117 9815102026 33972 44868 9277946053 74616+

а Tfe = бл/2 + eh+i/4: + • • крайне мало при больших h. [Журнал вычислительной математики и математической физики 6,2 (1966), 389-394. Аналогичные результаты для 2-3-деревьев были получены Э. М. Рейнгольдом (Е. М. Reingold), Fib. Quart. 17 (1979), 151-157.]

9. Эндрю Одлыжко (Andrew Odlyzko) показал, что количество сбалансированных деревьев асимптотически равно c"/(logjyjp 2)/3 где с я 1.916067 и f{x) = f{x + 1). Та же технология применима для поиска средней высоты. [См. статью Congressus ATumerantium 42 (1984), 27-52, в которой рассмотрен также перечень 2-3-деревьев.]

10. [Inf. Ргос. Letters 17 (1983), 17-20.] Пусть Xi, ..., Хл - узлы с заданными факторами сбалансированности В(Х*). Для построения дерева установим А; •<- О и вычислим TREE(oo), где TREE (Лтаж) представляет собой следующую рекурсивную процедуру с локальными переменными h,h uQ. Установить /г 4- О, Q Л; затем, пока h < hmax ик < N, присвоить ki-k + l,h<- h + ъак), LEFT(Xa) <- Q, RIGHT(Xa) 4-TREE(/i), h i- max{h,h) + l, Q (- X*; no окончании работы вернуть Q. (Дерево Q имеет высоту h и соответствует факторам сбалансированности, которые были прочитаны с момента входа в процедуру.) Алгоритм работает, даже если В(Х*) > 1.

11. Ясно, что при п > 2 имеется столько же узлов +А, сколько узлов -В и +-В, и между "+" и "-" существует симметрия. Если имеется М узлов типа +А или -А, рассмотрение всех возможных случаев для п > 1 показывает, что следующая случайная вставка с вероятностью ЗМ/(п + 1) приводит к уменьшению количества таких узлов на 1, а с вероятностью 1 - ЗМ/(п +1) - к увеличению их количества на 1. Отсюда можно получить требуемый результат. [SICOJVfP 8 (1979), 33-41; Курт Мельхорн (Kurt Mehlhorn) распространил анализ на случаи удаления из сбалансированных деревьев в работе SICOMP 11 (1982), 748-780. См. также работу R. А. Baeza-Yates, Computing Surveys 27 (1995), 109-119, в которой приводится сводка последних разработок в области такого анализа с использованием методов, проиллюстрированных в упр. 6.2.4-8.]