AOP_Tom1 (1021736), страница 158
Текст из файла (страница 158)
2,на то,что узлы 4 — 7 всегда располагаются в таком порядке. Этот результат можно получить автоматически методом индукции по рммеру бинарного дерева, 4. Он является реверсивным по отношению к обратному порядку обхода. (Это легко можно доказать по индукции.) Другой способ заключается в представлении пустого бинарного дерева в виде прямоугольника и в таком вращении представления для поддеревьев непустых бинарных деревьев, чтобы левые полдеревья располагались вперемешку слева или снизу от соответствующих правых поддеревьев в зависимости от четности очередного рекурсивного шага этого построения. В результате подобного построения прямоугольники будут соответствовать внешним узлам расширенного бинарного дерева (см, раздел 2.3.4.5).
Это представление, в значительной степени связанное с понятиями 2-мерных (2-г( (геев) и четырехмерных (г(пас)(геев) деревьев, которое обсуждается в разделе 6.5, особенно удобно использовать, когда информацию содержат внешние, а не внутренние узлы. б. Например, узлы дерева из упр. 2 в прямом порядке в двоичной системе (которая в данном случае эквивалентна десятичной системе обозначений Дьюи) выглядели бы так: 1, 10, 100, 101, 11, 110, 111. Здесь строки цифр рассортированы, как слова в словаре. Вообще, при лексикографической сортировке слева направо узлы будут перечисляться в прямом порядке, если "пропуск" < 0 < 1, в обратном порядке, если 0 < 1 < "пропуск", и в симметричном порядке, если 0 < "пропуск" < 1.
(Более того, если представить пропуски слева и рассмотреть ярлыки в десятичной системе обозначений Дьюи как обычные числа в двоичной системе счисления, получим порядок уровней (1еие1 отдет). см. 2.3.3 — (8) ) б. Тот факт, что последовательность ре рз... р, можно получить с помощью стека, легко доказывается методом индукции по и Действительно, нетрудно заметить, что именно зти действия выполняет стек в алгоритме Т (Ссютветствующая последовательность символов Я и Х, как в упр.
2.2.1-3, также соответствует последовательности цифр 1 и 2, которые используются в качестве индексов в двойноле порядке; см. упр. 18.) И наоборот, если последовательность рэ ..р„можно получить с помощью стека и если рл = 1, то р~...рл ~ является перестановкой (2,...,к) и рлл~...р †перестановк ()е+ 1,..., и). Эти перестановки соответствуют левому и правому поддеревьям, и их можно получить с помощью стека. Доказательство можно выполнить по индукции. 7. Используя прямой порядок, находим корень, а затем на основе симметричного порядка — левое и правое поддеревья Таким образом получим прямой и симметричный порядки этих поддеревьев.
Следовательно, структуру такого дерева можно легко восстановить (действительно, создание простого алгоритлэа восстановления структуры дерева по узлам, связанным в прямом порядке связями-нитями ШМК и в симметричном порядке связями-нитями НЪ1ИК, представляет собой довольно интересную задачу). Аналогично можно восстановить структуру дерева, зная симметричный и обратный порядки. Но знания прямого и обратного порядков недостаточно для восстановления структуры любого дерева, поскольку существует два бинарных дерева, которые выглядят, как АВ, в прямом порядке н, как ВА, в обратном порядке. Однако, ески все неконцевые узлы бинарного дерева имеют ио две непустые ветви, его структуру можно восстановить, зная прямой и обратный порядки 8. (а) Бинарные деревья со всеми пустыми связями ШНК.
(Ъ) Пустое бинарное дерево или дерево, содержащее только один узел (с) Бинарные деревья со всеми пустыми связями Н1.1ЫК. 9. Т1 выполняется один раэ, Т2 — 2п+1 раз, ТЗ вЂ” и раз, Т4 — и+1 раэ, Тб — и раз. Эти значения можно получить либо методом индукции, либо с помощью закона Кирхгофа, либо непосредственно анализируя программу Т. 10. При обходе бинарного дерева со всеми пустыми связями НЪ1КК потребуется поместить в стек адреса всех и узлов до того, как какие-либо из них будут удалены.
11. Пусть а„л — количество бинарных деревьев с и узлами, для которых стек в алгорит- ме Т никогда не содержит более 1' узлов. Если дл(е) = ~ „а„ля", то 9~(е) = 1/(1 — е), дэ(е) = 1/(1 — х/(1 — е)) = (1 — е)/(1 — 2е), ..., дл(э) = 1/(1 — хдл ~(е)) = Чл )(е)/дл(е), где Ч-~(е) = до(е) = 1, дел~(е) = дл(е) — едл е(е). Следовательно, 9л(е) = (Л (е)'+' — Уе(е)л+')/(У~(е)'эл — /е(е)'+'), где /э (э) = -'(1 х л/1 4е ).
Теперь можно показать, что а„л = [и )(1 — и)(1 + и) (1 — а ~ )/(1 — и ). Значит, в„= 2 >, )с(а„ь — а (а О) равно [и"+'[(1 — н)з(14.н)~" 2 >, н"/(1 — ну) минус а„„. Используя метод из упр. 5.2.2 — 52, получим асимптотический ряд 3 11 /л -з7з в„!а „= уГгяп ив — + — ~„/ — + 0(п ). 2 24)) и [Х.
С. де Вги))п, П. Е. Кпис1Ь апб Я. О. Гбсе, 1п СгарЬ ТЬеогу апд СотристК, ед. Ъу В С. Веас[ (ЬТеж ЪЪг)с: Асабеш)с Ргеш, 1972), 15 — 22.[ Если данное бинарное дерево представляет лес, описанный в разделе 2.3 2, то полученная величина является его емсогпай (Ье~дй() (т. е. наиболыпнм расстоянием между корнем и узлами дерева плюс один). Обобщения этого результата для других вариантов деревьев были получены Флажоле и Одлыжко [Х Сошригег апд Яуэгеш Яс[ 26 (1982), 171 — 213).
Асимптотическое распределение высоты вблизи и вдали от среднего значении проанализированы Флажоле, Гао, Одлыжко и Ричмондом [СошЬ)пасойсэ, РгоЬаЬ)1)гу, авс) Сошрийп8 2 (1993), 145-156[. 12. Узел ИООЕ(Р) следует посещать между шагами Т2 и ТЗ, а не между шагами Т4 и Т2. Чтобы доказать справедливость этого предложения, докажите истинность утверждения "Начиная с шага Т2 с ... исходным состоянием стека А, содержащим элементы А[1) .. А [гл)" точно так, как в тексте данного раздела. 13. (Решение принадлежит С.
Араухо (Я. Агай)о), 1976 ) Оставим шаги Т1-Т4 без изменений, но сделаем так, чтобы Ц инициализировалось значением Л на шаге Т1 и Ц указывало на последний посегденный узел, если такой имеется. Шаг Т5 заменим двумя другими шагами. Тб. [Правая ветвь пройдена?] Есин ИЬ1ИК(Р) = Л или КЬ1ИК(Р) = Ц, перейти к шагу Тб; в противном случае установить А ~ Р, Р < — КЬ1ИК(Р) и вернуться к шагу Т2. Тб.
[Попасть в Р,[ Попасть в узел ИООЕ(Р), установить Ц +- Р и вернуться к шагу Т4 Здесь применяется аналогичное доказательство. (Шаги Т4 и Т5 можно упростить таким образом, чтобы исключить операции извлечения узлов из стека с их немедленной повторной вставкой в стек.) 14. По методу индукции всегда существует в точности п+ 1 Л-связей (учитыввя Т, когда эта связь пуста). Так как с учетом Т существует и непугтых связей, замечание в данном разделе о преобладании пустых связей является справедливым. 15. Связь-нить 111ИК или КЬ1ИК указывает на узел тогда и только тогда, когда он имеет непустое правое или'левое поддерево соответственно (см. Рис. 24).
16. Если 1ТАСЬЦ) = О, то Цч=ШИК(Ц). Таким образом, узел Цч расположен на один шаг ниже и левее. В противном случае Цч можно найти, есин пройти вверх по дереву (если это необходимо) повторно до первой возможности перейти вниз и вправо беэ выполнения повторных шагов. Типичными примерами таких проходов являются пути от Р к Р* н от Ц к Цч в следующем дереве 1Т. Если ЬТАС(Р) = О, установить Ц +- ЬЬТИК(Р) и прекратить выполнение алгоритма. В противном случае установить Ц +- Р, затем ни разу или несколько раз устанавливать Ц +- НЕ1ИКОЦ) до тех пор, рока не будет соблюдено условие НТАС(Ц) = О. Наконец, еще один раз установить Ц < — Н,1ИК(Ц).
18. Измените алгоритм Т, вставив следующий шаг Т2.5: "Попасть в узел МООЕ(Р) (в первый раз)", а на шаге ТЬ узел ИООЕ(Р) будет посещен уже во второй раз. Обход прошитого дерева выполняется очень просто: (Р, 1) = (ШИК(Р), 1), если 1ТАС(Р) = О, в противном случае (Р,2); (Р,2) = (Н(.1ИК(Р), 1), если НТАС(Р) = О, в противном случае (Н11ИК(Р),2).
В любом случае в дереве происходит переход только на один шаг, поэтому на самом деле двойной порядок и значения Ы и е включаются в программу без явного упоминания. Опуская все посещения узлов в первый раз, получим в точности алгоритмы Т и Я, а опуская все посещения узлов во второй раз, получим решения упр. 12 и 17. 19. Основная идея заключается в поиске родителя Ц узла Р.
Если Р Ф ШИК(Ц), то получим Р) = Ц; в противном случае получим Рй повторно устанавливая Ц +- Цэ несколько раз (может быть, это вовсе не потребуется делать) до тех пор, пока не выполнится условие НТАС(Ц) = 1, (См., например, Р и Р( в показанном ниже дереве.) Для общего случая правопрошитого дерева не существует эффективного алгоритма поиска родителя узла Р, так как вырожденное правопрошитое дерево, в котором все левые связи пусты, является циклическим списком, в котором связи проведены в другом направлении. Следовательно, нельзя совершить обход правопрошитого дерева в обратном порядке с такой же эффективностью, как при использовании стека в упр.
13, без сохранения информации о пути к текущему узлу Р. Но если дерево прошито в обоих направлениях, родителя узла Р можно найти следующим достаточно эффективным способом. Е1. Установить Ц <- Р и Н <- Р. ЕХ. Если БОТАС(Ц) = АТАС(Н) = О, установитьЦ+- ШИК(Ц) ий <- Н).1ИК(Н) и повторить этот шаг.
В противном случае перейти к шагу Р4, если НТАС(Н) = 1. ЕЗ. Установить Ц +- ШИК(Ц) и пренратить выполнение алгоритма, если Р = Н(.1ИК(Ц). В противном случае не устанавливать или устанавливать Н е- Н1.1ИК(Н) до тех пор, пока не выполнится условие НТАС(Н) = 1; затем установить Ц <- М.1ИК(Н) и прекратить выполнение алгоритма. Е4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
