качестве такого указателя может выступать любой узел, расположение которого известно. [См. S. Huddleston and К. Mehlhorn, Acta Inf. 17 (1982), 157-184.]

32. При каждом вращении вправо увеличивается один из , не изменяя остальных, откуда Гк гк. Чтобы показать, что этого достаточно, предположим, что rj = rj для 1 < j < к, но < гк. Тогда существует вращение вправо, при котором увеличивается до значения < rk, потому что числа Г1Г2 .. .Гп удовлетворяют условию упр. 2.3.3-19, (а).

Примечание. Этот частичный порядок, впервые введенный в 1951 году Д. Тамари (D. Tamari), имеет .много интересных свойств. Любые два дерева имеют наибольщую нижнюю границу ТЛТ, определяемую размерами правых поддеревьев min(ri,ri) min(r2, гг)... min(r„,r), так же, как и наименьщая верхняя граница ТУТ определяется размерами левых поддеревьев min(Zi, Zi) min(Z2,1l) niin(/„, l). Размеры левых поддеревьев, конечно, на единицу меньше, чем поля RANK в алгоритмах В и С. За дополнительной информацией обратитесь к работам Н. Friedman and D. Tamari, J. CombinatoriaJ Theory 2 (1967), 215-242, 4 (1968), 201; C. Greene, Europ. J. Combinatorics 9 (1988), 225-240; D. D. Sleator, R. E. Tarjan, and W. P. Thurston, J, Amer. Math. Soc. 1 (1988), 647-681; J. M. Pallo, Theoreticai/nformatics and Applic. 27 (1993), 341-348; M. K. Bennett and G. Birkhoff, Algebra Universalis 32 (1994), 115-144; P. H. Edelman and V. Reiner, Mathematib, 43 (1996), 127-154.

33. Во-первых, можно свести объем памяти к одному биту А(Р) в каждом узле Р, такому, чтоВ(Р) = А (RLINK (Р)) - А (LLINK (Р)), когда LLINK (Р) и RLINK (Р) ненулевые; в противном случае В(Р) уже известно. Во-вторых, можно положить, что А(Р) = О, когда LLINK (Р) и RLINK (Р) нулевые. Тогда А(Р) может быть удален во всех других узлах после обмена LLINK(Р) с RLINK(P) при А(Р) = 1; сравнением KEY(Р) с KEY(LLINK(P)) или KEY(RLINK(P)) определяется А(Р).

Естественно, на машинах, указатели которых всегда четны, каждый узел имеет два неиспользуемых бита. Чтобы получить дополнительную экономию памяти, следует поступить, как в упр. 2.3.1-37.

РАЗДЕЛ 6.2.4

1. Разделяются два узла:

2. Измененные узлы:

□□□□ □□□□

f~cot--4 ео-нг---!

О- - сО ю CD t-оа CNtcoiOCD

EDCDCDCD CDtDCDCD t-b-t-t-

□DOOQ Qdl

□DDDD

(Конечно, В*-дерево могло бы и не иметь узлов с тремя ключами, хотя на рис. 30 они показаны.)

3. (а) 1 + 2 • 50 + 2 51 • 50 + 2 • 51 • 51 • 50 = 2 • 51 - 1 = 265301.

(b) 1 + 2 50 + (2 • 51 • 100 - 100) + ((2 • 51 • 101 - 100) • 100 - 100) = 101 = 1030301.

(c) 1 + 2 • 66 + (2 67 • 66 + 2) + (2 67 • 67 66 + 2 • 67) = 601661. (Меньше, чем (Ь)!)

4. Перед разделением некорневого узла убедитесь, что он имеет два заполненных соседа. Затем разделите эти три узла на четыре. Корень должен разделяться только тогда, когда в нем содержится больше 3 [(Зт - 3)/4j ключей.

5. Интерпретация 1, попытка максимизировать сформулированную задачу дает 450. (Наихудшая ситуация возникает при наличии 1 005 символов и передаваемого родительскому узлу ключа длиной 50: 445 символов + указатель + 50-символьный ключ + указатель + 50-символьный ключ + указатель + 445 символов.)

Интерпретация 2, попытка уравнять количество ключей после разделения для поддержания высокого ветвления: 155 (15 коротких ключей, за которыми следуют 16 длинных). См. Е. М. McCreight, САСМ 20 (1977), 670-674.

6. Если удаляемый ключ находится не на уровне 1-1, замените его ключом-наследником и удалите последний. Для удаления ключа на уровне / - 1 достаточно просто стереть его; если при этом узел окажется слишком пустым, обратитесь к его правому (или левому) соседу и выполните "вливание" т. е. переместите ключи в узел из соседа таким образом, чтобы в обоих узлах содержалось примерно одинаковое количество данных. Такая операция невозможна только при малой заполненности соседа; в этом же случае можно объединить два узла в один (вместе с одним ключом из родительского узла). Такое объединение может, в свою очередь, вызвать необходимость вливания на уровне родительского узла и т. д. При наличии ключей переменной длины, как в упр. 5, может потребоваться разделение родительского узла (когда один из его ключей становится длиннее).

8. Имея дерево Т с N внутренними узлами, обозначим через о- внешние узлы, тре-буюш;ие к обраш;ений, родительские узлы которых относятся к страницам, содержаш;им j ключей. Пусть также A\z) является соответствуюш;ей производяш;ей функцией. Тогда A\1) +----h Al) = N+1. (Заметим, что о- кратно j + 1 при 1 < j < М.) Следующая случайная вставка приводит к появлению N+1 равновероятного дерева, производящие функции которых получаются путем уменьшения некоторых коэффициентов о[- на j-Ь1 и прибавления j+2 к а* (или, если j - М, уменьшения некоторых о!" на 1 и прибавления 2 к о,). Теперь В(г) равно {N + 1)~, умноженному на сумму производящих функций Л(г) для Т, умноженных на вероятность появления Т по всем деревьям Т. Отсюда следуют такие сформулированные рекуррентные соотношения:

(В1;)(г),.. .,B\z)Y = iI+{N + irW{z))iB<iiUz), BZ\iz)f = ---=gNiW{z)){0,...,0,lf,

Значит, = (1,..., l)(Bi,(l),.. .,B/{l)f = 2B\(l)/(iV+ 1) + С-г = 2/;v(W)mm, где fn{x) = gn-i{x)/{n+l)+- • +go{x)/2 = (gn{x)-l)/x и W = W{1). (Индекс MM означает нижний левый угол матрицы.) Теперь W = diag (Ai,..., Am)-? для некоторой матрицы S, где diag (Ai,..., Am) обозначает диагональную матрицу, элементами которой являются корни полинома х(А) = {Х + 2)... {Х + М + 1) - {М + 1)1. (Все корни различны, поскольку

х(А) = xW - О приводит к 1/(А--2)-------1/(А--М--1) = 0; это может выполняться только

тогда, когда А действительно и -М-1 < А < -2, откуда вытекает, что А--2... А--М--1 <

(М + 1)!, а это противоречит начальному условию.) Если р{х) - некоторый полином, то р{\¥) = р(5~ diag (Ai,..., Xm)S) = diag (p(Ai),... ,р{Хм))3; следовательно, правый

нижний элемент p(W) имеет видс1р(А1)Н-----1-смр(Ам), где некоторые константы ci,... ,см

не зависят от р. Эти константы можно вычислить, положив р(А) = xW/i ~ •i)i так как (W*)mm = (-2)* приО < а; < М-1, имеемp(W)mm =р(-2) = (M+l)!/(Aj+2) = с,р(А,) = CiX(Aj) =Cj(M + l)!(l/(Aj+2) + -.- + l/(Aj + M + l)). Значит, с,- = (А,-+ 2)-(l/(Aj + 2) +

-----l/(Aj+M+l))~\ Это дает "точную" формулу Cjv = Ej=i 2c>/Af(Aj); остается только

исследовать корни Aj. Заметим, что Aj + М + 1 < М + 1 для всех j, иначе мы бы имели Aj + 2... Aj + М + 1 > (М + 1)!. Взяв Ai = О, убеждаемся, что K(Aj) < О для 2 < j < М. Согласно 1.2.5-(15) дп(х) ~ (п + 1)Г(ж + 2) при п -> оо; следовательно, pn(Aj) О для 2<j<M. Таким образом, Cn = 2ci/n(0) + 0(1) = Hn/{Hm+i - 1) + 0{1).

Примечание. Приведенный анализ применим также к алгоритму простой сортировки, вкратце обсуждавшемуся в разделе 5.2.2. Вычисления могут быть легко дополнены для того, чтобы показать, что Bj(l) ~ (Ям+i - 1)~70 + 2) при 1 < j < М и В(1) ~ {Нм+1 - 1)~/2. Поэтому общее количество внутренних узлов в незаполненных страницах приблизительно равно

/ 1 2 М-1 N N / М \

их2"4хЗ"""(М+1)хМ/Ям+1-1 ~ V (М+1)(Ям+1-1)/

а общее количество использованных страниц примерно равно

/ 1 1 1 1 N

Ux2""4x3"""""(M+1)xM""M+1/:

(М+1)хММ+1;Ям+1-1 2(Ям+1-1)

откуда следует, что асимптотическое использование памяти равно 2{Нм+\ - 1)/М.

Этот анализ был развит в работе Махмуда (Mahmoud) и Питтеля (Pittel) [J. Algorithms 10 (1989), 52-75], которые открыли, что дисперсия количества использованной памяти подвергается неожиданному фазовому переходу: при М < 25 дисперсия равна G(iV), но при М > 26 она асимптотически равна /(iV)iV+°, где /(eiV) = f{N), если - + а + /Зг и - 1 + Q - /Зг являются ненулевыми корнями Aj с наибольшей действительной частью.

Высота таких деревьев проанализирована в работах L. Devroye, Random Structures and Algorithms 1 (1990), 191-203, и В. Pittel, Random Structures and Algorithms 5 (1994), 337-347.

9. Да; например, мы могли бы заменить каждое Ki в (1) на г плюс число ключей в поддеревьях Ро,... ,Pi-i. Соответствующим образом изменяются алгоритмы поиска, встгшки и удаления.

10. Краткий набросок: расширим страничную схему так, чтобы исключительный доступ к буферам предоставлялся только одному пользователю одновременно. Алгоритмы поиска, вставки и удаления должны быть тщательно модифицированы, чтобы такой исключительный доступ предоставлялся только на ограниченное время, только при крайней необходимости и таким образом, чтобы не возникало клинчей. За подробностями обратитесь к работам В. Samadi, Inf. Proc. Letters 5 (1976), 107-112; R. Bayer and M. Schkolnick, Acta Inf. 9 (1977), 1-21; Y. Sagiv, J. Сотр. Syst. Sci. 33 (1986), 275-296.

РАЗДЕЛ 6.3

1. Отблески. (На самом деле перед нами непереводимая игра слов, основанная на близости слов tree и trie. В связи с этим ниже приводится текст оригинала упражнения и ответа к нему. - Прим. перев.

If а tree has leaves, what does a trie have?

Lieves (the plural of "lief").)