12. Максимально возможное время достигается при вставке во второй внешний узел (12); С = 4, С1 = 3, D = 3, А = С2 = F = G\ = HI = U1 = 1, и общее время равно 132и. Минимум достигается при вставке в третий от конца внешний узел (13); С = 2, С1 = С2 = 1, £) = 2, и общее время равно 61и. (Соответствующие параметры программы 6.2.2Т равны 74и и 26и.)

13. При изменениях дерева должны обновляться только 0(log N) значений RANK; "упрощенная" система может потребовать большего количества изменений.

14. Да (хотя типичные операции над списками весьма неслучайны и вероятность появления вырожденных деревьев достаточно высока).

15. Воспользуйтесь алгоритмом 6.2.2Т с установкой m О на шаге Т1 и m m4-RANK(P) при К > KEY(P) на шаге Т2.

16. Удалим Е; выполним ребалансировку (случай 3) в D. Удалим G; заменим F на G; выполним ребалансировку (случай 2) в Н; откорректируем фактор сбалансированности в К.

17. (а)

19. (Решение Кларка Крейна (Clark Crane).) Имеется один случай, который не может быть сведен к однократному или двукратному повороту в корне. В этом случае следует

заменить на

++ С

а затем избавиться от несбалансированности с помощью однократного или двукратного поворота в С.

20. Очень сложно вставить новый узел в крайнюю слева позицию показанного дерева:

однако К.-Ю. Ряйхя (K.-J. Raiha) и С. Г. Цвебен (S. Н. Zweben) разработали алгоритм вставки, который требует 0(log N) шагов [САСМ 22 (1979), 508-512].

21. Алгоритм А выполняет задание за Alog шагов (см. упр. 5); описанный далее алгоритм создает такое же дерево за 0{N) шагов при помощи интересной итеративной реализации рекурсивного метода. Мы используем три вспомогательных списка:

Dl,..., D; (бинарный счетчик, который управляет рекурсией);

Ji,..., Jj (список указателей на стыковочные узлы);

Tl,... ,Т; (список указателей на деревья).

Здесь I = \lg{N+1)]. Для удобства алгоритм также устанавливает Do 1, Jo J/+i Л.

GI. [Инициализация.] Установить Z •<- о, Jo •<- Ji •<- л, Dq •<- 1.

G2. [Получить следующий элемент.] Пусть Р указывает на следующий входящий узел (для его получения может использоваться другая программа). Если новых узлов больше нет, переходим к шагу 05. В противном случае установить к <- 1, Q <- А и заменить Р Ji.

G3. [Продолжение.] Если к > I (или, что то же самое, Р = Л), установить I <- I + 1, Uk <- 1, Та <- Q, Зк+1 -«-Ли вернуться к шагу 02. В противном случае установить D*: <г- 1 - Uk, заменить Q Т*,, Р •<-> J+i и увеличить к на 1. Если теперь dk-i = о, повторить этот шаг.

G4. [Конкатенация.] Установить LLINK(Р) <- Ik, RLINK(Р) (- Q, В(Р) (- о, Т* <- Р и вернуться к шагу 02.

G5. [Завершение.] Установить LLINKCJ*) <- Tj,, RLINKCJ*) 4- J-i, ВОк) <r- 1 - Da i для 1 < A: < Л Алгоритм завершен (J; указывает на корень искомого дерева).

Шаг G3 выполняется 2ЛГ - u{N) раз, где u{N) - число единиц в двоичном представлении числа N.

22. Высота взвешенно-сбалансированного дерева с Л внутренними узлами всегда лежит межд> lg(A +1) и 2 lg(A+1). Для получения верхней границы заметьте, что более тяжелое поддерево корня имеет не более (Л + 1)/\/2 внешних узлов.

23. (а) Постройте дерево, правое поддерево которого представляет собой полное бинарное дерево с 2" - 1 узлами, а левое - дерево Фибоначчи с Fn+i - 1 узлами. (Ь) Постройте взвешенно-сбалансированное дерево, правое поддерево которого имеет высоту порядка 21gA, а левое - порядка IgA (см. упр. 22).

24. Рассмотрим наименьшее дерево, удовлетворяющее условию, но не являющееся идеально сбалансированным. Тогда его левое и правое поддеревья идеально сбалансированы и соответственно количество их внешних узлов составляет 2 и 2, где I фг, что противоречит заданному условию.

25. После вставки узла в нижнюю часть дерева мы движемся вверх, проверяя весовой баланс в каждом узле на пути поиска. Предположим, что в узле А в (1) имеется несбалансированность, а новый узел вставлен в правое поддерево, где В и ею поддеревья взвешенно-сбалансированы. Тогда после однократного поворота баланс восстановится, если (q + /3)/7 > \/2 + 1, где \х\ означает число внешних узлов в дереве х. Однако можно показать, что в этом случае достаточно двукратного поворота [см. SICOMP 2 (1973), 33-43].

27. Иногда в узлах с двумя ключами необходимо выполнить два сравнения. Наихудший случай встречается в деревьях, подобных изображенному, когда в некоторых ситуациях требуется 2 lg(A -Ь 2) - 2 сравнений.

29. Частичное решение, принадлежащее Э. Яо (А. Yao), таково: для Л > 6 ключей нижний уровень будет содержать в среднем f (Л + 1) узлов с одним ключом и (Л + 1) узлов - с двумя ключами. Общее среднее количество узлов при больших Л лежит между 0.70iV и 0.79N. [Acta Informatica 9 (1978), 159-170.]

30. Для случая наилучшего подходящего упорядочите записи по размерам по произвольному правилу связывания областей с одним и тем же размером (см. упр. 2.5-9). В случае первого подходящего упорядочите записи по адресам с дополнительным полем в каждом узле, содержащем размер наибольшей области в поддереве, для которого данный узел является корнем. Эти поля могут обновляться при вставках и удалениях. (Впрочем, хотя время работы и оказывается равным 0(log п), вероятно, на практике метод блужданий из упр. 2.5-6 будет более эффективным. Однако без ROVER память может распределяться еще лучше, так как обычно "на всякий пожарный" поддерживается свободной область памяти больиюго объема.)

В работе R. Р. Brent, АСМ Trans. Prog. Languages and Systems 11 (1989), 388-403, можно ознакомиться с усовершенствованием описанного метода.

31. Используйте почти сбалансированное дерево с дополнительными связями вверх для крайней слева части и стек отложенных корректировок фактора сбалансированности вдоль этого пути (для каждой вставки требуется ограниченное число таких корректировок).

Эта задача может быть обобщена на случай использования О (log m) шагов для поиска, вставки и/или удаления элементов, которые находятся в т шагах от данного "указателя"; в