Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 30
Текст из файла (страница 30)
Слитором и Р. Е. Таржаном (дАСМ 32 (1985), 652-686). Они основаны на идеях, подобных используемым при эвристических перемещениях и перестановках (см. раздел 6.1). Данная технология была исследована Б. Алленом (В. АИеп) н Дж. Муиро (3. Мппго) (,УАСМ 25 (1978), 526-535), а также Дж. Битнером (Л. В!спет) (ЯХСОМР 8 (1979), 82-110[. Вытянутые деревья, подобно другим видам уже упоминавшихся сбалансированных деревьев, поддерживают операции как вставки и удаления, так и конкатенации н разделения, причем достаточно простым образом.
Более того, время, необходимое дяя доступа к данным в вытянутом дереве, не превышает времени доступа в статически оптимальном дереве, умноженного на некоторую небольшую константу (в установившемся режиме после серии операций с деревом). Слитор и Таржан предположили, что О61цее время доступа в вытянутом дереве не превышает оптимального времени доступа к данным н времени, необходимого для выполнения динамических поворотов согласно любому алгоритму работы с бинарными деревьями, умноженного на константу.
Рандомизацня позволяет использовать методы, даже более быстрые и простые, чем вытянутые деревья. Жан Вуйлемеи (.1еап ЪН111еш1п) [САСМ 23 (1980), 229-239] ввел понятие декаршавмх деревьев (сагГеэ1ап Егееэ), в которых каждый узел имеет два ключа (х,у). Часть х упорядочена слева направо, как в бинарных деревьях поиска; часть у упорядочена сверху вниз, как в случае приоритетной очереди (см. раздел 5.2.3).
С. Р. Арагон (С. В. Агакоп) и Р. Г. Зайдель (В. С. Белйе1) присвоили таким структурам данных очень цветастое название ггеар, которое получено в результате комбинирования частей слов ггееэ и 11еарз. (Видимо, наилучший русский термин должен звучать как дума — от дерева и кучи, — Прим. перев.) Только одна дуча может быть пост1юена на Основе и данных пар ключей (х1 у1) у . ° °, (ха ~ уа) ~ если все х и у различны.
Один из путей получения лучи — вставка х согласно алгоритму 6.2.2Т в соответствии с порядком у. Однако имеется еще один простой алгоритм для непосредственной вставки любых новых пар в лучу. Арагон и Зайдель обнаружили [РОС8 30 (1989), 540-546[, что, если х представляют собой обычные ключи, а у выбираются случайным образом, можно быть уверенным, что дуча имеет внд случайного бинарного дерева поиска. В частности, дуча со случайными значениями у всегда будет сбалансирована, за исключением случая экспоненцивльно малой вероятности (см. упр.
5.2.2-42). Арагон и Зайдель также показали, что дучи могут быть легко "скошены", так что, например, ключ х с относительной частотой 7 будет располагаться вблизи корня в соответствии со своей частотой, если с ним будет ассоциирована величина у = С111, где С вЂ” случайное число между 0 н 1. Дучи, в целом, предпочтительнее вытянутых деревьев, как показали некоторые проведенные Д. Э. Кнутом эксперименты, связанные с расчетами выпуклых оболочек [,7АСМ 46 (1998), 288-323]. Ф В следующее издание книги планируется добавить раздел 6.2.5, посвншенный рандозтзнровалным структурам данных. В нем будут рассмотрены списки с пропускамн [И'.
Рнйб, САСМ 33 (1990), 668-67б~, рандомизнронанние бинарные деревья поиска ($. Воига апд С. Маггшех, ЛАСМ 45 (1998), 288-3231, а также упомянутые в этом разделе "дучн". УПРАЖНЕНИЯ 1. [01] почему в случае 2 в (1) нельзя просто поменять местами левые поддеревья узлов А и В? 2. [16) Обьясните, почему, если достигнут шаг А? с В($) = О, дерево становится на один уровень выше.
° 3. [Мйб) Докажите, что сбалансированное дерева с Ж внутренними узлами не может содержать более (8 — ЦК ж 0,6180ЗЖ узлов с ненулевыми факторами сбалансированности. 4. [МЗЙ] Докажите или опровергните следующее утверждение; среди всех сбалансированных деревьев с Рьы — 1 внутренними узлами дерево Фибоначчи порядка Ь имеет наибольшую длину внутреннего пути. ° 5, [МЮБ) Докажите или опровергните следующее утверждение: если для последовательной вставки ключей Км, .., Кч в дерево, изначально содержащее только ключ К~ (К~ < К> « ..
Кя), используется алгоритм А, то полученное дерево всегда опшимально (т. е. имеет минимальную длину внутреннего пути среди всех бинарных деревьев с Ю узлами). 8. [М21) Докахсите, что (5) определяет производящую функцию для сбалансированных деревьев высотой Ь. 7. [МЕ?) (Н, Дж. А. Слоан (В, 1. А. Я)папе) и А. В. Ахо (А. У. АЬо).) Докажите замечательную формулу (9) для числа сбалансированных деревьев высотой Ь. (Указание. Положим, что С„= В„+ В„м н используем тот факт, что!об(С„~.~/С~в) очень малб при больших и.) 8. [М24[ (Л.
А, Хиздер.) Покажите, что существует константаб, такая, что В,',(Ц/Вл(Ц ж 2> — 1 + 0(2ь/Вь 1) при Ь -Ф оо. 9. [ВМее) Чему равна асимптотическое число сбалансированных бинарных деревьев с и внутренкнми узлами 2 „>е Веь? Чему равна асимптотнческая средняя высота ~ „>е ЬВьь/ /2 ь>оВ л? ь 10. [37] (Р. К. Ричардс (Н. С. НлсЬагбе).) Покажите, что сбалансированное дерево может быть единственным образом построено по списку его факторов сбалансированности 3(ЦВ(2) ...
8(А?) в симметричном порядке. 11. [М24) (Марк Р. Браун (Мшй Н. Вгони).) Докажите, что прн и > 6 среднее количество внешних узлов каждого из типов +1, -1, ь+И, +-В, -+В, — В составляет в точности (и+ 1)/14 для случайньи сбалансированных деревьев с и внутренними узлами, гюстроеннмх по алгоритму А. ь 12. [Е() Чему равно максимально возможное время работы программы А при вставке восьмого узла в сбалансированное дерево? Чему равно минимальное время для етого случая? 13.
[Об) Почему поле ИАНК лучше использовать так, как указано в тексте, а не хранить индекс каждого"узла в качестве его ключа (иазывая первый узел "Г', второй — "'2" и т. д.)? 14. [М) Можно лн адаптировать алгоритмы 6.2.2Т и 6.2.2П для работы с линейными списками с использованием поля Иайй, как зто было сделано для алгоритмов работы со сбалансированными деревьями? 15.
[18) (К. А. Крейн (С. А. Сгапе).) Предположим, что упорядоченный линейный список представлен в виде бияарного дерева с полями КЕТ и ИЬИИ в каждом узле. Разработайте алгоритм, который осуществляет поиск в дереве данного ключа К и определяет его положение в списке, т. е. находит число гп, такое, что меньше К лишь т — 1 ключей. ° 16. [20) Нарисуйте сбалансированное дерево, которое получается после удаления узла Е и корневого узла Г из дерева, показанного на рис. 20, с использованием предложенного в тексте алгоритма. ь 11. [21) Нарисуйте сбалансированное дерево, которое получается после конкатенации дерева Фибоначчи (12): (а) справа и (Ь) слева от дерева, показанного на рнс.
20, с помощью предложенного в тексте алгоритма конкатенации. 18. [22] Нарисуйте сбалансированные деревья, которые получаются после разделения дерева, показаняого на рнс. 20, на две части ((А,..., Ц и (1,...,Я)) с использованием предложенкого в тексте алгоритма. ° 19. [26] Найдите способ преобразования данного сбалансированного дерева так, ггобы фактор сбалансированности в корне не бмл равным -1. При этом должен сохраняться симметричный порядок узлов и должно поро;кцаться искомое сбалансированное дерево за 0(Ц единиц времени независима от количества узлов в исходном дереве.
20. [46] Рассмотрите идею использования ограиичекного класса сбелансированнмх деревьев с факторами сбалансированности, равными 0 нлп +1 (в этом случае поле В может свестись к одному биту). Существует ли для таких деревьев процедура вставки с разумной эффектявностьюу ь 21. [60] (Идеальная 6елансороека.) Разработайте алгоритм построения бинарных деревьев с Х узлами, которые оптимальны в смысле упр. о.
Он должен выполкяться за 0(Х) шагов н быть "последовательным", т. е. вы должны получать узлы по одному в порядке возрастания н строить частичные деревья по ходу, не зная окончательного значения уэ' (такой алгоритм может пригодиться для перестройки плохо сбалансированного дерева или прк слиянии двух деревьев в адно). 22. [МЙО) Каков аналог теоремы А для взвешенно-сбалансированных деревьев? 23. [МЯО] (Э. Рейнгольд (Е. Ке!пйо!6),) Покажите, что между сбалансированными по высоте и взвешенно-сбалансированными деревьями не существует простой взаимосвязи.
а) Докажите, что существуют сбалансированные по высоте деревья со скаль угодно малым отношением (вес левого поддерева) Днес правого поддерева) в смысле (17). Ь) Докажите, что существуют взвешенно-сбалансированные деревья, имеянцие скольугодно большую разность между высотой левого и правого нодлеревьев. 24. [М22) (Э.
Рейнгольд.) Докажите, что если усилить условие (17) до 1 левый вес — < <2, 2 правый вес то ему будут удовлетворять только идеально сбалансированные бинарные деревья с 2" — 1 внутренними узлами. (В таких деревьях левые и правые веса в каждом узле равны между собой.) 23. [27] (Ю. Нивергельт (Л. Х!еэегбе!1), Э. Рейнгольд и Ч. Вонг (С. %опй).) Покажите, что можно разработать алгоритм вставки во взвешенно-сбалансированные деревья с со- хранением условия (17), амполняющий не более 0(1с 8 Х) поворотов на вставку. 20.
[60] Исследуйте свойства сбалансированных барных деревьев прн ! > 2. ь 27. [М23] Оцените максимальное количество сравнений, необходимых для поиска в 2-3- дереве с Ф внутренними узлами. 28. Щ Реаяизуйте алгоритмы работы с 2-3-деревьями программно с достаточной эф- фективностью. 29. [М67] Проанализируйте поведение 2-3-деревьев в среднем при случайных вставках.
30, [26) (Э. Мак-Крейт (Е. 3(сСгшбЬС).) В разделе 2.5 обсуждался ряд стратегий динами- ческого распределения памяти, включая метод наилучшего подходящего (Ьевс-б!) (выбор области наименьшего размера, удовлетворяющей запросу) и метод первого подходящего (бгэс-бс) (выбор области с яаименьшим адресом, удовлетворяющей запросу).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
