Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 102
Текст из файла (страница 102)
Со к [Вг"). Обобщение результатов для двойных зкспоненциалъных последовательностей приводится в Г!Ьопасс! Оиаг«ег)у 11 (1973), 429-437. Выражение для 6 быстро сходится к значению В = 1.43687 28483 94461 87э80 04279 84335 54862 92481+, 8. Пусть Ьл = Влс(1)/Вл(1) + 1 и пусть сл = 2ВлВл-с(Ьл — Ьл-с)/Влас. Тогда Ьс = 2, Ьллс = 2Ьл — ел и сл = О(Ьл/Вл- с); следовательно, Ьл = 2"!) + гл, где = 1 — 1сс — ос« — = 0,7011798151020263397244868927794605374616+ а гл = сл/2+ сл«с/4+ крайне мало при больших Ь. [Журнал вычислительной математики и математической физики 6,2 (1966), 389-394. Аналогичные результаты для 2-3-деревьев были получены Э.
М. Рейнгольдом (Е. М. ))спп8о!6), Р)Ь. ()ив«с. 17 (1979), 151-157.) 9. Эндрю Одлыжко (Апбгело Об!ув)со) показал, что количество сбалансированных деревьев асимптотически равно с" /(1об -,— и)/и, где с 1.916067 и /(к) = /(к+ 1). Та же технология применима для поиска средней высоты. [См. статью Сопбгевоиз №щегапбиш 42 (1984), 27 — 52, в которой рассмотрен также перечень 2-3-деревьев.) 10. [1пг. Ргос, ъеИегз 17 (1983), 17-20.[ Пусть Хм..., Хк — узлы с заданшями факторами сбалансированности В(Хл) .
Для построения дерева установим Ь с- 0 н вычяслим ТВЕЕ(оа), где ТЙЕЕ(Ьиса«) представляет собой следующую рекурсивную процедуру с локальными переменными Ь, Ь' и О. Установить Ь +- О, О +- Л: затем, пока Ь < Ьти«и Ь < Аг, присвоить Ь +- А+ 1, Ь' +- Ь+ В(Хл), БЕТТ(Х*) +- Ц, ЕТОВТ(Хл) с- ТВЕБ(Ь ), Ь +- щах(Ь, Ь ) + 1, О+- Хл, по окончании рабаты вернуть Ц. (Дерево О имеет высоту Ь и соответствует факторам сбалансированности, которые были прочитаны с момента входа в процедуру.) Алгоритм работает, даже если [В(Хл) ) > 1. 11.
Ясно, что при и > 2 имеется сталъко же узлов +Ь, сколько узлов — В и +-В, н между "+" н "-' существует симметрия. Ешщ пмеется М узлов типа+вили -Ь, рассмотрение всех возможных случаев для и > 1 показывает, что следующая случайная вставка г. вероятностью ЗМ/(и + 1) приводит к уменьшению количества таких узлов на 1, а с вероятиостъю 1 — ЗМ/(и + 1) — к увеличению их количества нв 1. Отсюда можно получить требуемый результат. [о)СОЬ)Р 8 (1979), 33-41, Курт Мелъхорн (Китс МеЫЬогп) распространил анализ на случаи удаления из сбалансированных деревьев в работе Ь)СОМР 11 (1982), 748 — 780. См.
также работу К. А. Вас«а- с'асео, Сощрио!вб битл"сук 27 (1995), 109-119, в которой приводится сводка последних разработок в области такого анализа с использованием методов, проиллюстрированных в упр. 6.2.4 — 8.[ 12. Максимально возможное время достигается прн вставке во второй внешний узел (12); С = 4, С1 = 3, В = 3, А = С2 = Р = 01 = гТ1 = С1 =. 1, и общее время равно 132о. Минимум достигается при вставке в третий от конца внешний узел (13); С = 2, С1 = С2 = 1, )У = 2, и общее время равно 61и. (Соответствующие параметры программы 6.2.2Т равны 74и и 26и.) 13. При изменениях дерева должны обновляться только 0((об Ф) значений ККИК; "упрощенная" система может потребовать большего количества язменений.
14. Да (хотя типичные операпии над списками весьма неслучайны и вероятность появления вырожденных деревьев достаточно высока). 16. Воспользуйтесь алгоритмом 6 2 2Т с установкой го +- 0 на шаге Т1 и т +- таККИК(Р) при К > КЕУ(Р) на шаге Т2. 16. Удалям Е, выполним ребалансировку («лучей 3) в Р. Удалим 6; заменим Р на 6; выполним ребаланснровку (случай 2) в Н; откорректируем фактор сбалансированности в К. 19. (Решение Кларка Крейна (С1шк Стане).) Нмеется один случай, который не может быть сведен к однократному или двукратному повороту в корне.
В атом случае следует заменить на а затем избавиться от несбалансированности с помощью однократного или двукратного поворота в С. 29. Очень сложно вставить новый узел в крайнюю слева позицию покезанного дерева: однако К.-)О. Ркйхя (К.-Л. ВюЬа) и С. Г. Цвебен (Б. Н. ЕнеЬев) разработали алгоритм вставки, который требует 0(1об Ф) шагов [САСЫ 22 (1979), 598-512[. 21. Алгоритм А выполняет задание за Ж )об Ж шагов (см. упр. 5); описанный далее алгоритм создает такое же дерево за 0()У) шагов прн помощи интересной итеративной реализации рекурсивного метода. Мы используем три вспомогательных спкскш Вм..., 9» (бинарный счетчик, который управляет рекурсией); Юм..., Л~ (список указателей на стыковочные узлы); Тм...,Т~ (список указателей на деревья). Здесь 1 = [19(Я+1) [.
Длк удобства алгоритм также устанавливает Ре»- 1, Ле»- )~+~ +- А. О1. [Инициализация.) Установить 1»- О, Ле +- Л» +- А, Ое»- 1. О2. [получить следующий злемент.] пусть Р указывает на следуюпшй входящий узел (для его получения может использоваться лругая программа). Если новых узлов больше нет, переходим к шагу Сб.
В противном случае установить л+- 1, 9+- Л и заменить Р ++ ) ь ОЗ. [Продолжение.) Если к > 1 (или, что то же самое, Р = Л), установить 1»- 1+ 1, О»»- 1, Т»»- Я, Л»»»»- А и вернуться к шагу О2. В противном случае установить Р» +-1 — О», заменить Ц е» Т», Р+» )»+» и увеличить я на 1. Если теперь Р»» — — О, повторить зтот шаг, О4. [Конкатенация.[ Установять 12.1ИИ(Р) +- Т»„ИЫИК(Р) +- Я, В(Р) +- О, Т»»- Р и вернутьск к шагу 02. Сб. [Завершение.[ Установить !Л,ПЖ()») +- Т», ИУ.1ИКИ»)»- д» м 9(Л») +- 1 - О»-» для 1 < й < Е Алгоритм завершен (Л~ указывает на корень искомого дерева).
$ Шаг 03 выполняетск 2Ю вЂ” и(Ф) раз, где и(Ф) — число единиц в двоичном представлении числа Х. 22. Высота взвешенно-сбалансированного дерева с Х внутренними узлами всегда лежит между !8(Я+1) и 2 !8(й'+ 1). Для получения верхней гранины заметьте, что более тяжелое поддерево корня имеет не более ()!" + 1)/ъ72 внешних узлов. 23. (в) Постройте дерево, правое поддерево которого представляет собой полное бинарное дерево с 2" — 1 узлами, а левое — дерево Фибоначчи с Р +~ - 1 узлами.
(Ь) Постройте взвешенно-сбалансированное дерево, правое полдерево которого имеет высоту порядка 2 !8)т', а левое — порядка!8)!! (см. упр. 22). 24. Рассмотрим наименьшее дерево, удовлетворяющее условию, но не являющееся идеально сбалансированным. Тогда его левое н правое поддеревья идеально сбалансированы н соответственно количество их внешних узлов составляет 2' и 2", где ! ф г, что противоречит заданному условию. 28.
После вставки узла в нижнюю часть дерева мы движемся вверх, проверяя весовой баланс в юмклом узле на пути поиска. Предположим, что в узле А в (1) имеется несбалансированность, а новый узел вставлен в правое поддерево, где В и ево поддерееья взвешенно-сбалансированы. Тогда после однократного поворота баланс восстановится, если ((а(+ )!1!)/(7! > ~/2+ 1, где (х) означает число внешних узлов в дереве х, Однако можно показать, что в этом случае достаточно двукратного поворота (см.
ЯСОМР 2 (1973), 33-43). 27. Иногда в узлах с двумя ключами необходимо выполнить лва сравнения, Наихудший случай встречается в деревьях, подобных изображенному, когда в некоторых ситуациях требуется 2 !8(лг+ 2) — 2 сравнений. 29. Частичное решение, принадлежащее Э. Яо (А. Ъ'ао), таково: для )т' > 6 ключей нижний уровень будет содерхшть в среднем 7(!з'+ 1) узлов с одним ключом и -"()т'+ 1) узлов — с двуми ключами. Общее среднее количество узлов при больших л1 лежит между 0.70Ю и 0.79дг. (Асса 1лЕоппа!!са 9 (1978), !$9-170.) 30. Для случая наилучшего подходящего упорядочите записи по размерам по произвольному правилу связывания областей с одним и тем же размером (см, упр. 2.5-9). В случае первого подходящего упорядочите записи по адресам с дополнительным полем а кюкдом узле, содержащем размер наибольшей области в поддереве, для которого данный узел является корнем.
Эти поля могут обновляться при вставках и удалениях, (Впрочем, хоти время работы и оказывается равным О(1об и), вероятно, на практике метод блужданий из упр. 2.5-0 будет более эффективным. Однако без 80988 память может распределяться еще лучше, так как обычно "на всякий похшрный" поддерживается свободной область памяти большого объема.) В Работе !1, Р. Вгеве, АСМ Тгвва Ргоб. 7апбнабеэ апд 8!акела 11 (1989), 388-403, можно ознакомиться с усовершенствованием описанного метода. 31.
Используйте почти сбалансированное дерево с дополнительными связями вверх для крайней слева части и стек отложенных корректировок фактора сбалансированности вдоль этого пути (для каждой вставки требуется ограниченное число таких корректировок). Эта задача может быть обобщена на случай использования О(!об гл) шагов длк поиска, вставки и(или удалении элементов, которые находятся в ш шагах от данного "указателя"; в качестве такого указателя может выступать любой узел, расположение которого известно.
[См. Я. НпгИ1ев1оп щн1 К. МеЬ)Лога, Асса )лб 17 (1982), 157-184.) 32, При каждом вращении вправо увеличивается один из гы не изменяя остальных, откуда г„< г„. Чтобы показать, что этого достаточно, предположим, что г, = г, для 1 < ) < Ь, по гь < гь. Тогда существует вращение вправо, при котором г„, увеличивается до значения < гго потому что числа г1ге .. г„удовлетворяют условию упр. 2.3.3 — 19, (а). Примечание. Этот частичный порядок, впервые введенный в 1951 году Д. Тамарн (1).
Тешат)), имеет много интересных свойств. Любые два дерева имеют наибольшую нижнюю гранину ТАТ', определяемую размерами правых поддеревьев ппп(гм г; ) ппп(гм гэ)... ппп(гь, г'„), так же, как н наименьшая верхняя граница Т Ч Т' определяеггя размерами левых поддеревьев ппп(1„1',) ппп(1э, (э)... ппп(1„, 1'„). Размеры левых поддеревьев, конечно, на единицу меньше, чем поля ВАСК в алгоритмах В и С. За дополнительной информацией обратитесь к работам Н. гг1ег)шап аш) 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
