AOP_Tom3 (1021738), страница 204
Текст из файла (страница 204)
(Конкатенация.) Установить 11ХИК(Р) е- Ты Ж.1ИИ(Р) +- 9, В(Р) Э- О, Ть +- Р и вернуться к шагу С2. Сб. (Завершение,) Установить 11ХИИ(уь) ь — Ть, Ы.1ИИ(уэ) +- уь и В(уь) +- 1 — Оь-~ для 1 < й < !. Алюритм завершен (у~ указывает на корень искомого дерева). З Шаг СЗ выполняется 2Л! — и(М) раз, где н()У) — число единиц в двоичном представлении числа Лг.
22. Высота взвешенно-сбалансированного дерева с Х внутренними узлами всегда лежит между (8(К+ 1) и 2 !8(Х+ 1). Для получения верхней границы заметьте, что более тяжелое поддерево корня имеет не более (Ж+ 1)/»/2 внешних узлои. 23. (а) Постройте дерево, правое поддерево которого представляет собой полное бинарное дерево с 2" — 1 узлами, а левое — дерево»рибоначчи с 5'„.»» — 1 узлами. (Ь) Постройте взвешенно-сбалансированное дерево, правое поддерево которого имеет высоту порядка 2 !8/»», а левое — порядка )8Е!» (см упр.
22). 24. Рассмотрим наименьшее дерево, удовлетворяющее условию, но не являющееся идеально сбалансированиыл», Тогда его левое и правое поддеревья идеально сбалансированы и соответственно количество их внешних узлов составляет 2 и 2, где ! ЭЬ г, что противоречит заданному условию. 26. После вставки узла в нижнюю часть дерева мы движемся вверх, проверяя весовой баланс в каждом узле на пути поиска. Предположим, что в узле А в (Ц имеется несбалансированност»ч а новый узел вставлен в правое поддерево, где В и ево полдеревья взвешенно-сбалансированы. Тогда после однократного поворота баланс восстановится, если ((и(+ !»9()/(7! >»/2+ 1, где (х! означает число внешних узлов в дереве х. Однако можно показать, что в этом случае достаточно двукратного поворота (см.
ЯСОМР 2 (1973), 33-43). 27. Иногда в узлах с двумя ключами необходимо выполнить два сравнения. Наихудший случай встречается в деревьях, подобных изображенному, когда в некоторых ситуациях требуется 2 !8(»»~ + 2) — 2 сравнений. 29. Частичное решение, прииадлев»ашее Э. Яо (А. Уао), таково; для Х > б ключей нижний уровень будет содержать в среднем 1(Л + 1) узлов с одним ключом и у»(Х+ 1) узлов — с двумя ключами.
Общее среднее количество узлов при больших Х лежит между 0.70!»Е и 0.797»». (Ас»а Ел1оппабса 9 (1978), 159-170.) 30. Для случая наилучшего подходящего упорядочите записи по размерам по произвольному правилу связывания областей с одним и тем же размером (см. упр. 2.5 — 9). В случае первого подходящего упорядочите записи по адресам с дополнительным полем в каждом узле, содержащем размер наибольшей области в поддереве, для которого данный узел является корнем. Эти поля могут обновляться при вставках и удалениях. (Впрочем, хотя время работы и оказывается равным О(!обо), вероятно, на практике метод блужданий из упр. 2.5-б будет более эффективным. Однако без 80»ЕЕй память может распределяться еще лучше, так как обычно "на всякий пожарный" поддерживаетск свободной область памяти большого объема.) В работе К. Р.
Вгеп», АС5Е Тгапэ. Ргоб. Йапбиабеэ ап»Е Був»еп»э 11 (1989), 388-403, можно ознакомиться с усовершенствованием описанного метода. 31. Используйте почти сбалансированное дерево с дополнительными связями вверх для крайней слева части и стек отложенных корректировок фактора сбалансированности вдоль этого пути (для каждой вставки требуется ограниченное число таких корректировок). Эта задача может быть обобщена на случай использования О(!об т) шагов для поиска, вставки и/или удючения элементов, которые находятся в ьч шагах от данного "указателя"; в качестве такого указателя может выступать любой узел, расположение которого известно. (См.
К Нойс(!ее!оп апб К. 1(еЬ!Ьогп, АсСа Хлб 17 (1982), 157-184.) 32. Нри каждом вращении вправо увеличивается один из гю пе изменяя остальных, откуда гь < гг, Чтобы показать, что этого достаточно, предположим, что г, = г', для 1 < )' < 1г, но гь < г'„. Тогда существует вращение вправо, при котором гь увеличивается до значения ( г'„, потому что числа г~ гв ., г„удовлетворяют условию упр. 2.3.3 -19, (а). Примечание. Этот частичный порядок, впервые введенный в 1951 году Д.
Тамарн (!). Тагпап), имеет много интересных свойств. Любые два дерева имеют наиболыпую нижнюю границу ТЛ Т', определяемую размерами правых поддеревьев пнп(г,, г,) пнп(гм гэ) . тт(г, г'„) „так же, как и нанменыпая верхняя граница Т иТ' определяется размерами левых поддеревьев т!п(1„1',) пцп(1п!в) .. т!и(1„, 1'„) Размеры левых поддеревьев, конечно, на единицу меньше, чем паля ВАМК в алгоритмах В и С. За дополнительной информацией обратитесь к работам Н. Рпейпап апб (). Татаг(, Х СоглЬ(ла(ог(а1 ТЬеогу 2 (1967), 215-242, 4 (1968), 201; С.
Сгеепе, Енгор. 1. СотЬ!ла!ог)св 9 (1988), 225 -240; П П. Б!еа!ог., К Е. Тат)ап, апб )гг'. Р. Т!гага!оп, Х Апзег. МаГЬ. Бос. 1 (1988), 647 — 681; д. М. Ра!!о, Т1~еогег(са) 1пГогглаВсв алЯ Аррбс. 27 (1993), 341 -348, М К. Веппет апд С. В!гЬЬоЯ, А18еЬга (Глл егвайв 32 (1994), 115 — 144; Р. Н. Ебе!гоап апг( У. Кетег, МвейетаН)га 43 (1996), 127-! 54. ЗЗ. Во-первых, можно свести объем памяти к одному биту А(Р) в каждом узле Р, такому, что В(Р) = А(КЬ)ИК(Р) ) — А(Е11ИК(Р)), когда ШИК(Р) н КЬ1ИК(Р) ненуловые; в противном случае В(Р) уже известно. Во-вторых, можно положить, что А(Р) = О, когда ШИК(Р) и КЬКИК(Р) нулевые.
Тогда А(Р) может быть удален во всех других узлах после обмена Ы.1МК(Р) с 81.1ИК(Р) при А(Р) = 1; сравнением КЕУ(Р) с ХЕУ(ШМК(Р)) или КЕУ(КЬ1ИК(Р)) определяется А(Р). Естественно, на машинах, указатели которых всегда четны, каждый узел имеет два неиспользуемых бита. Чтобы получить дополнительную экономию памяти, следует поступить, как в упр. 2.3 1-37. РАЗДЕЛ 6.2.4 1. Разделяются два узла: 2. Измененные узлы; (Конечно, В -дерево могло бы и не иметь узлов с тремя ключами, хотя на рис.
30 они показаны. ) 3. (а) 1+ 2. 50+ 2 51 50+ 2 51 51 50 = 2 51 — 1 = 265301. (Ь) 1 + 2 . 50 + (2 51 100 — 100) + ((2 51 101 — 100) 100 — 100) 1011 1030301 (с) 1+ 2 66-(- (2 67 66+ 2) + (2 67. 67 66+ 2. 67) = 601661. (Меньше, чел» (Ь)!) 4. Перед разделением некорневого узла убедитесь, что он имеет два заполненных соседа. Затем разделите эти три узла на четыре. Корень должен разделяться только тогда, когда в нем содержится болыне 3 ((Зт — 3)/4) ключей.
5. Интерпретация 1, попытка максимизировать сформулировы»ную задачу дает 450. (Наихудшая ситуация возникает при наличии 1005 символов и передаваемого родительскому узлу ключа длиной 50: 445 символов + указатель + 50-символьный ключ + указатель + 50-символьный ключ + указатель + 445 символов.) Интерпретасщи 2, попытка уравнять количество ключей после разделения для поддержания высокого ветвления: 155 (15 коротких ключей, за которыми сяедуют 16 длинных). См. Е. М. МсСге(5Ь», САСМ 20 (1977), 670-674.
6. Егли удаляемый ключ находится не иа уровне 1 — 1, замените его ключом-нагледником и удалите последний. Для удаления ключа на уровне 1 — 1 достаточно просто стереть его; если при этом узел окажется слишком пустым, обратитесь к его правому (или левому) соседу и выполните "вливание", т. е. переместите ключи в узел из соседа таким образом, чтобы в обоих узлах содсржалось примерно одинаковое количество данных.
Такая операция невозможна только при малой заполненности соседа; в этом же случае можно объединить два узла в один (вместе с одним ключом из родительского узла). Такое объединение может, в свою очередь, вызвать необходимость вливания на уровне родительского узла и т. д.
При наличии ключей переменной длины, как в упр. 5, может потребоваться разделение родительского узла (когда один из его ключей становится длиннее). 0. Имея дерево Т с Х внутренними узлами, обозначим через а~' внешние узлы, требующие 7» обращений, родительские узлы которых относятся к страницам, содержащим 1 ключей. пусть также А~»~(г) является соответствующей производящей функцией, тогда .4(')(1) + + А(м)(1) = Х+ 1. (Заметим, что о(ь) кратно 7+ 1 при 1 < у < М) Следующая случайная вставка приводит к появлению Х+1 равновероятного дерева, производящие функции которых получаются путем уменьшения некоторых коэффициентов а11 на 1+1 и О) прибавления д 52 к а(1 ) (или, если 1' = М, уменьшения некоторых а(ь' ) на 1 и прибавления ()э1) (и) 2 к аь»1). ТепеРь Вн (з) Равно (Х+ 1), Умпоженнол»У на сУммУ пРоизводвщих фУнкций (1) (1) -1 А(1)(з) для T, умноженных на вероятность появления T по всем деревьям 7 Отсюда следуют такие сформулированные рекуррентные соотношения: (В")(,),...,В,', )( ))' = (7+ (Х+ ц-'И (з))(В(,"1(.),...,В, ')(,))' = дн((4 ( )ИО,...,0,1)~, где Значит, Сч — — (1,..., 1)(В»» (1),..., Вй '(1)) = 2В„, (1)/(Х+ 1) + С,'», — — 2/ч(И')мм, где / (з) = д 1(х)/(о+1)+ +да(х)/2 = (д„(х)-1)/х и И' = И'(1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
