AOP_Tom3 (1021738), страница 132
Текст из файла (страница 132)
Мвггтех,,7АСМ 45 (1998), 288-3231, а также упомянутые в этом разделе "дучн? УПРАЖНЕНИЯ 1. (01) Почему в случае 2 в (1) нельзя просто поменять местами левые подлеревья узлов А н В? 2. (16] Объясните, почему, если достигнут шаг А? с В13) = О, дерево становится на один уровень выше. 3. [М25] Докажите, что сбалансированное дерево с Ас внутренними узлами не может содержать более (с) — 1)А 0,61803)7 узлов с ненулевыми факторами сбалансированности. 4. [М22] Докажите нли опровергните следующее утверждение: среди всех сбалансированных деревьев с Рлз.с — 1 внутренними узлами дерево Фибоначчи порядка Л имеет наибольшую длину внутреннего пути. 5.
[М25] Докажите или опровергните следующее утверждение: если для последовательной вставки ключей Км, Кл в дерево, изначально содержапсее только ключ Кс (Кс ( Кз < < Ки), используется алгорспм А, то полученное дерево всегда аптпмальна (т. е. имеет минимальную длину внутреннего пути среди всех бинарных деревьев с 17 узлами). 6. [М21] Докажите, что (5) определяет производящую функцию для сбалансированных деревьев высотой Л. 7. [М27) (Н. Днс.
А. Слоан (з(. 1. А, Я!папе) и А. В. Ахо (А. 'сс. АЬо).) Докажите замечательную формулу (9) для числа сбалансированных деревьев высотой Л. (Указание. Положим, что С = В + В с, и используем тот факт, что!об(С +с/Сз) очень мало при больших и.) 8. [М2а] (Л, А, Хиздер.) Покажите, что существует константа/1, такая, что Вс„(1)/Вл(1) = 2~17 — 1+ 0(2~/Вл с) при Л вЂ” л ж. 9.
[ВМ11] Чему равно асимптотическое число сбалансированных бинарных деревьев с и внутренними узлами 2 л>а В„л? Чему равна асимптотическая средняя высота 2 а ЛВал/ /Е аВл ь 10. [27] (Р. К. Ричардс (Н. С. Н(сЬагс)з).) Покажите, что сбалансированное дерево может быть единственным образом построено по списку его факторов сбалансированности В(1)В(2)... В(Ас) в силсметрнчном порядке. 11. [М21] (Марк Р. Браун (Маг!с Н. Вгочсп).) Докажите. что прн и > б среднее количество внешних узлов каждого из типов +А, -А, ++В, +-В, -+В, — В составляет в точности (и+ 1)/14 для случайных сбалансированных деревьев с и внутренними узлами, построенных по алгоритму А. ь 12.
[24] Чему равно максимально возмовсное время работы программы А при вставке восьмого узла в сбалансированное дерево? Чему равно минимальное время для этого случая? 13. [05] Почему поле КАКК лучше использовать так, как указано в тексте, а не хранить индекс каждого'узла в качестве его ключа (называя первый узел "1", второй — "2" н т.
д.)? 14. [!1] Можно ли адаптировать алгоритмы 6.2.2Т и 5.2.2П для работы с линейными списками с использованием поля КАИК, как это было сделано для алгоритмов работы со сбалансированными деревьями? 15. [18] (К. А. Крейн (С. А. Сгапе).) Предположим, что упорядоченный линейный список представлен в виде бинарного дерева с полями КЕТ и КАВК в каждом узле. Разработайте алгоритм, который осуществляет поиск в дереве данного ключа К и определяет его положение в списке, т, е.
находит число га, такое, что меньше К лишь пс — 1 ключей. ь 16. ]20] Нарисуйте сбалансированное дерево, которое получается после удаления узла Е и корневого узла Е из дерева, показанного на рнс. 20, с использованием предложенного в тексте алгоритма. Ь 17. [21] Нарисуйте сбалансированное дерево, которое получается после конкатенации дерева Фибоначчн (12): (а) справа и (Ь) слева от дерева, показанного на рис. 20, с помощью предложенного в тексте алгоритма конкатенации. 18.
[22] Нарисуйте сбалансированные деревья, которые получаются после разделения дерева, показанного на рис. 20, на две части ([А,...,1) и (Л,..., Ц)) с использованием предложенного в тексте алгоритма. ь 19. [25] Найдите способ преобразования данного сбалансированного дерева так, чтобы фактор сбалансированности в корне не был равным — 1. При этом должен сохршгяться симметричный порядок узлов и должно порождаться искомое сбалансированное дерево за 0(1) единиц времени независимо от количества узлов в исходном дереве. 20. [40] Рассмотрите идею использования ограниченного класса сбалансированных деревьев с факторами сбалансированности, .равными б нли +1 (в этом случае поле 3 может свестись к одному биту). Существует ли для таких деревьев процедура вставки с разумной эффективностью? ь 21.
[ЗО] (Идеальнил балансировка.) Разработайте алгоритм построения бинарных деревьев с ?г' узлами, которые оптимальны в смысле упр. 5. Он должен выполняться за 0()г') шагов и быть "погледовательным") т. е. вы дачжны получать узлы по одному в порядке возрастания и строить частичные деревья по ходу, не зная окончательного значения Ж (такой алгоритм может пригодиться для перестройки плохо сбалансированного дерева илн прн слиянии двух деревьев в одно). 23. [М20] Каков аналог теоремы А для взвешенно-сбалансировюгных деревьев? 23.
[М20] (Э. Рейнгольд (Е. ЙешбоЫ).) Покажите, что мещлу сбалансированными по высоте и взвешенно-сбалансированнымн деревьями не существует простой взаимосвязи. а) Докахсите, что существуют сбалансированные по высоте деревья со сколь угодно малым отношением (вес левого поддерева)/(вес правого поддерева) в смысле (17). Ь) Докажите, что существуют взвешенно-сбалансированные деревья, имеющие сколь угодно большую разность между высотой левого н правого поддеревьев. 24. [М22] (Э.
Рейнгольд.) Докажите, что если усилить условие (17) до 1 левый вес — < <2, 2 правый вес то ему будут удовлетворять только идеально сбалансированные бинарные деревья с 2" — 1 внутренними узлами. (В таких деревьях левые и правые веса в каждом узле равны между собой.) 25. '„27! (Ю. Нивергельт (Л. Жечегбе!Г), Э. Рейнгольд н Ч. Вонг (С. УРопб).) Покажите, что можно разработать алгоритм вставки во взвешенно-сбалансированные деревья с со- хранением условия (17), выполняющий не более О(!об йг) поворотов на вставку. 26. [40] Исследуйте свойства сбалансированных барных деревьев при ! > 2.
и 37. [М2З] Оцените максимальное количество сравнений, необходимых для поиска в 2-3- дереве г Х внутренними узламн. 28. [41] Реализуйте алгоритмы работы с 2-3-деревьями программно с достаточной эф- фективностью. 39. [М47] Проанализируйте поведение 2-3-деревьев в среднем при случайных вставках. 30. [2б] (Э. 51ак-Крейт (Е. МсСге!8Ьг).) В разделе 2.5 обсуждался ряд стратегий динами- ческого распределения памяти, включая метод наилучшего подходящего (Ьеэ1-бг) (выбор области наименьшего размера, удовлетворяющей запросу) и метод первого подходящего (бгэс-бг) (выбор области с наименьшим адресом, удовлетворяющей запросу).
Покажите, что если свободное пространство связано в сбалансированное дерево, то можно найти как (а) наилучшую подходящую, так и (Ь) первую подходящую области за О(!обо) единиц времени, где и — — количество доступных областей (алгорнтмы из раздела 2.5 выполняют поставленную задачу за 0(п) шагов). 31, (34) (КЬ Л. Фредман (э1 Ь. Ргебшап), 1975.) Придумайте представление линейных списков, такое, что вставка нового элемента между позициями тп — 1 и тп при данном гп требует 0(1оя гп) единиц времени. 32.
(МЯ7) Даны лва бинарных дерева с и уэламя — Т и Т'. Будем говорить, что Тб Т', если Т' может быть получено иэ Т с помощью последовательности нэ нуля или нескольких поворотов вправо. Докажите. что Т х Т' тогда и только тогда, когда г„< г'„для 1 < й < и, где гк и гк означают соответственно размеры правых поддеревьев й-х узлов (в симметричном порядке) деревьев Т и ТЬ ь ЗЗ. (35) (А. Л. Бухсбаум (А. Ь. ВасйэЬаат).) Поясните, каким образом можно неявно закодировать фактор сбалансированности АЪ'Ь-дерева для сохранения двух битов на узел эа счет дополнительной работы при обращении к дереву. И велел СамУил подкоднть воем коленам ИзРаилевым, н указано колено Вениаминова.
И велел подходить колену Вениаминову по племенам его, н указано племя МатпнЕво; и пРиводят племя Матрнеео по мужам, и назван Саул, сын Кисея; н искали его, и не находили. — ПеРвая книга Цаоств, 10мэа-21 6.2.4. Сильиоветвищиеси деревья Обсуждавшиеся выше методы лаиска были разрабатаны, в первую очередь, для внутреннего поиска, когда выполняется просмотр таблицы, целиком содержащейся в высокоскоростной внутренней памяти. Теперь рассмотрим внешний поиск, когда нужно получить информацию из очень большого файла, расположенного на внешних запоминающих устройствах с прямым доступом, таких как диски и барабаны (о дисках и барабанах можно прочесть в разделе 5.4.9). Древовидные структуры довольно удобны для внешнега поиска, если выбрать подходящий способ представления дерева. Рассмотрим большое бинарное дерево поиска, показанное на рис.
29, и представим, чта оно хранится в дисковом файле (поля ЬЬТКК и НЬ1МК теперь представляют собой адреса на диске, а не во внутренней памяти). Если наивно проводить поиск в таком дереве так же, как в случае внутреннего поиска, нам понадобится около )КХ обращений к диску для выполнения одного поиска. При Х, равном миллиону, это означает порядка 20 обращений к диску. Однако стоит разделить таблицу на 7-узельные "страницы", как показано на рис. 29. и при доступе к одной странице эа один раз потребуется примерно в три раза меньше обращений к диску, т. е, практически поиск ускорится в три раза! Группиравание узлов в страницы фактически приводит к преобразованию бинарнога дерева в кактарнае" с разветвлением в каждой странице-узле на 8 путей.
Если страницы будут иметь ббльшие размеры, с разветвлением на 128 путей паоле каждого обращения к диску, та поиск элемента в таблице с миллионом элементов завершится при просмотре исего лишь трех страниц. Можно постоянно хранить корневую страницу во внутренней памяти, так чта потребуются лишь два обращения к диску (при этом ва внутренней памяти одновременна будет находиться не более 254 ключей). Рис. 29.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
