Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 112
Текст из файла (страница 112)
Полное т-арное ориентированное дерево высоты и имеет вершин и ть листьев. В частности, полное бинарное ориентированное дерево высоты и имеет 2ь+' — 1 вершин и 2" листьев. ДОКАЗАТЕЛЬСТВО. Поскольку число вершин на каждом уровне в гп раз больше, чем на предыдущем, это приводит к геометрической прогрессии, поэтому т-арное ориентированное дерево высоты и имеет л "' 1+т+гп +т + +т +т т — 1 вершин. Поскольку листьями являются только те вершины, которые находятся на уровне Й, их насчитывается т". Доказательство следуюшей теоремы предоставляется читателю.
ТЕОРЕМА 15.9. а) Если полное гп-арное дерево высоты й имеет 1 листьев, то гг = 1оя (1). б) Если т-арное дерево высоты и имеет 1 листьев, то и > 1оя (1). в) Если полное бинарное дерево высоты и имеет о вершин, то и = 1оя (о+1) — 1. г) Если бинаРное деРево высоты и имеет о веРшин, то и > 1ойз(о+ 1) — 1. Напомним, что функция 1' из графа С(Ъ; Е) в граф С'(Ъ",Е') назывется гомоморфизмом из С в С', обозначается г': С вЂ” С', если она обладает следующими свойствами. Напомним также, что гомоморфизм 1: С вЂ” С' является изоморфизмом, если г': 1' — ~" и г": Š— Е' являются взаимно однозначными соответствиями.
Если )': С вЂ” С' изоморфизм, то говорят, что С и С' изоморфны. ОПРЕДЕЛЕНИЕ 15.11. Два корневых бинарных дерева Т(Е, Ъ') и Т'(Е',Ъ") изоморфны, если существует изоморфизм )' из Т в Т' такой, что а) о; — левый сын вершины оу тогда и только тогда, когда г"1о,) — левый сын вершины г'1о ). б) о, — правый сын вершины ьу тогда и только тогда, когда у'(о,) — правый сын вершины Г'1оу). в) г' отображает корень г дерева Т в корень г' дерева Т'. Любителям заниматься подсчетами предлагаем следующую теорему. ТЕОРЕМА 15.12.
Число неизоморфных корневых бинарных деревьев с п вершинами равно числу Каталана С„. 628 ГЛАВА 15. Деревья ДОКАЗАТЕЛЬСТВО. Пусть 1„— число изоморфных корневых бинарных деревьев с п вершинами. Если и = О, имеем пустое дерево и полагаем 1о = 1. Если и = 1, имеем одну вершину и, очевидно, только одно дерево, поэтому 1, = 1. Если п = 2, имеем два корневых бинарных дерева, изображенных на рис. 15.!.
Если п = 3, имеем пять корневых бинарных дерева, изображенных на рис. 15.2. Рис. Ы2 Рис. 15.1 Предположим, что и ) 3, и выберем такое к, что 1 < )с < и. Пусть Т„обозначает дерево с и вершинами и пусть Т„» — дерево с п вершинами, определенное следуюшим образом. Поскольку одна вершина является корнем, предположим, что имеются правое поддерево Т»» с и — 1 вершиной и левое поддерево Т„» с и — к вершинами, как показано на рис.
15.3. Рис. Ы.З Тогда по определению число способов, которыми можно построить дерево Т» ы равно 1» ы а число способов, которыми можно построить дерево Т„», равно 1„». Таким образом, число способов построения Т„» равно 1»» 1„». Суммируя по к, получаем число всевозможных способов построения дерева Т„. Итак, что совпадает с определением числа Каталана С„. Поэтому 1 (2п)! 1„= С„= — . и+1 и! и! ° УПРАЖНЕНИЯ 1. Найдите неизоморфные корневые бинарные деревья с п вершинами: когда а) и=2; б) и=3; в) и=4.
2. Сколько существует неизоморфных корневых бинарных деревьев с и вершинами: а) п=5; б) п = 6; в) и=8; г) и=10; д) и=20. РАЗДЕЛ 15, 1. Свойства деревьев 629 3. Сколько в полном т-арном дереве высоты й имеется листьев, вершин и внутренних вершин при условии: а) т=2и6=5; б) тп=Зи 6=4; а) т=2и6=8; г) т=4 и 6=3; д) т=1ип=10.
4. Для дерева, изображенного на рис. 15.4, определите; (1) высоту корневого дерева; (й) уровень вершины е; (й() уровень вершины д; (1ч) уровень вершины а; (ч) какая вершина является родителем ю'; (в1) какие вершины являются сыновьями вершины 6 а) если корнем выбрана вершина д; б) если корнем выбрана вершина Г'; в) если корнем выбрана вершина с; г) если корнем выбрана вершина З; д) если корнем выбрана вершина 6. Ь Рис. !5.5 Рис.
!5.4 5. Для дерева, изображенного на рис. 15.5, определите: (1) высоту корневого дерева; (й) уровень вершины е; (й)) уровень вершины д; (Ь) уровень вершины а; (ч) какая вершина является родителем г'; (ч1) какие вершины являются сыновьями вершины 6 а) если корнем выбрана вершина с(; б) если корнем выбрана вершина !; 630 ГЛАВА т5. Деревья в) если корнем выбрана вершина с; г) если корнем выбрана вершина ?; д) если корнем выбрана вершина Ь.
6. Какие из приведенных ниже деревьев являются сбалансированными? Какие из них являются полными? б) в) г) а д) Л й е деревьев являются сбалансированными? Какие 7. Какие из приведенных ниже из них являются полными? а) б) а в) а а У" е ге И1 1 г) д) а е Г 8. При условии, что полное бинарное дерево имеет 32 листа, определите: а) высоту этого дерева; б) количество вершин. 9. При условии, что полное бинарное дерево имеет 128 листьев, определите: а) высоту этого дерева; б) количество вершин. 10. Докажите, что а) для полного гп-арного дерева высоты 6 с 1 листьями Ь = 1ок (!); б) для полного пт-арного дерева высоты й с 1 листьями 6 > 1оя (1); в) для полного бинарного дерева высоты 6 с числом вершин, равным о, й = 1обз(е + 1) — 1.
Рдздеп15.2. Бинарные деревья поиска 631 11. Докажите теорему !5.9 а) для полного гп-арного дерева высоты Ь с ! листьями Й = !о5 (!). б) для полного т-арного дерева высоты Ь с ! листьями Ь > !об (!). в) для полного бинарного дерева высоты Ь с числом вершин, равным и, Ь = !ояз(и + 1) — 1. г) для бинарного дерева высоты Ь, имеющего и вершин, Ь > !ояз(и+1) — 1. 12. Докажите, что дерево с двумя или более вершинами является двудольным графом. 13. Докажите, что связный граф является деревом тогда и только тогда, когда добавление нового ребра между вершинами графа всегда приводит к возникновению цикла. 14. Докажите или опровергните, что связный граф является деревом тогда и только тогда, когда каждое его ребро является разрезающим ребром. 15. Докажите или опровергните, что связный граф является деревом тогда и только тогда, когда каждая его вершина является разрезающей вершиной.
16. Какие вершины в корневом дереве являются разрезающими? 17. Пусть С вЂ” связный граф. Сформулируйте необходимые и достаточные условия того, что удаление из графа С любого ребра превращает его в дерево. 18. Пусть Т(Ъ', Е) — корневое дерево. Определим отношение < на Ъ' как а < Ь, если а = Ь или а — потомок Ь. Покажите, что отношение < есть частичный порядок. Определим произведение а Ь = нвг(а, Ь), так что (Ъ', ) — верхняя полурешетка. Опишите а 6 в терминах путей из вершин а и 6 в корень. 19. Пусть ТЯ, Е) — корневое дерево. На Ъ' определено умножение, как в предыдущем упражнении. Для заданной вершины а из Ъ' определим а: Ъ' — Ъ' как а(и) = аи. Докажите, что а — гомоморфизм полугрупп.
15.2. БИНАРНЫЕ ДЕРЕВЬЯ ПОИСКА Бинарное корневое дерево, которое назовем просто бинарным деревом, обеспечивает прекрасный метод организации данных, при котором любые конкретные данные можно легко найти или установить их отсутствие. Очевидно, что самый неэффективный способ поиска — последовательный просмотр всех данных, так как если необходимые данные отсутствуют, то для установления этого факта нужно просмотреть весь список.
Бинарное дерево поиска позволяет избежать этого. Единственным требованием является введение на данных некоторого линейного порядка. Этим порядком может быть, к примеру, алфавитный или числовой порядок. Линейный порядок может быть на теге, указателе, файле или некотором другом ключе, определяющем данные. Но нас будет интересовать только наличие некоторого линейного порядка. Для простоты примем расположение имен в алфавитном порядке. Бинарное дерево поиска — это прежде всего бинарное дерево, в каждом узле которого находится имя (или другой ключ). Рассмотрим построение бинарного дерева поиска.
В процессе построения станет понятно, как использовать это дерево. Предположим, что необходимо запомнить имена: Петерсон, Джонсон, Смит, Вейл, Спенсер, Рассел, Бауэр, Мартин, Уилсон и Лайман. 632 ГЛАВА 15. Деревья Начинаем с имени Петерсон и помещаем его в корень дерева. Поскольку следующее имя, Джонсон, в алфавитном порядке стоит перед именем Петерсон, делаем Джонсона левым сыном Петерсона, как показано на рис. 15.6. Следующее имя, Смит, в алфавитном порядке стоит после имени Петерсон, поэтому имя Смит становится правым сыном имени Петерсон, как показано на рис.
15.7. Петерсон Джонсон Рис. 15.7 Рис. 15.5 Теперь рассмотрим имя Вейл. В алфавитном порядке имя Вейл стоит перед (или меньше, чем) именем Петерсон, спускаемся к левому сыну, Джонсону, и поскольку в алфавитном порядке имя Вейл расположено перед именем Джонсон, делаем Вейла левым сыном Джонсона, как показано на рис. 15.8. Далее рассматриваем имя Спенсер. Поскольку в алфавитном порядке имя Спенсер идет после имени Петерсон, спускаемся к правому сыну, Смиту. Но так как в алфавитном порядке имя Спенсер расположено после имени Смита, делаем Спенсера правым сыном Смита, как показано на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
