Опр. Если каждая вершина ордерева имеет не более 2-х потомков, то дерево называют бинарным (двоичным).
Ясно, что возникают понятия левого и правого потомка (левого и правого поддерева)
Префиксный код бинарного ордерева.
Каждой вершине ордерева (кроме корня (мы сопоставим двоичное число. Левому потомку корня мы припишем 0, а правому 1, потомкам 00 и 01 соответственно и т.д.
Достаточно хранить в памяти компьютера не все построенные числа, а только расположенные на висячих вершинах, слева направо.
{000, 010, 011, 10, 110, 1110, 1111} – это и есть префиксный вид бинарного дерева.
Он определяет ордерево однозначною по нему можно восстановить бинарное дерево.
Каждое их чисел В в перфективном коде позволяет однозначно восстановить весь путь от корня до висячей вершины, тем самым все ордерево.
Заметим, что для больших деревьев префексивный код очень объемен. Если у бинарного ордерева 10 уровней, то возникает 10-битовые двоичные числа, в количестве до 1024. Поэтому пробуем получить более компактные способы представление ордеревьев и деревьев в памяти, заодно отказавшись от требования бинарности.
Замечание: аналогично бинарным 3-арные, n-арные деревья, но для них все гораздо сложнее. Желательно иметь более компактные способы кодирования в памяти, пригодные не только для бинарных, но и для любых деревьев ордеревьев.
Код Прюфера.
Немецкий математик К.Прюфер изобрёл способ представления любых деревьев и ордеревьев. Изложим алгоритм построения кода Прюфера.
Пусть имеется дерево с n пронумерованными вершинами. В списке всех вершин слева направо ищем первую висячую вершину. Пусть это a1. Ищем единственную вершину b1 с которой смежна a1. Величину b1 заносим в новый список – будущий код Прюфера, а вершину a1 вычеркиваем и из списка, и из дерева. Этот процесс повторяем n-2 раза. В результате получим новый список. {b1, b2,…, bn-2} – это и есть код Прюфера. Заметим, что в процессе построения дерево все время уменьшается, и возникают новые висячие вершины
Пример.
Построить код Прюфера для дерева.
Список всех вершн 1 2 3 4 5 6 7.
N=7; отсюда n-2=5.
В этом списке слева направо ищем первую висячую.
{1; 1; 6; 2; 6;} – код Прюфера.
Доказано, что код Прюфера определяет дерево однозначно. Более того, любой список { b1, b2,..,bn-2} чисел от 1 до n является кодом Прюфера некоторого дерева.
Пример 2.
Восстановить дерево по коду Прюфера.
{1; 3; 6; 5; 3; 2; 7;}
n-2=7; n=9.
1 2 3 4 5 6 7 8 9
Введем понятие неприкосновенной вершины: если вершина встречается в коде Прюфера дальше, то она неприкосновенна
Добавляем оставшиеся вершины.
Перестроим дерево.
Теорема Кэш.
Общее число деревьев с n пронумерованными вершинами равно nn-2/
Доказательство.
Таких деревьев ровно столько, сколько кодов Прюфера. b – число от 1 до n.
По правилу произведения nn-2
Например, для n=5, получим 55-2=152 раз.
Обход деревьев.
Часто необходимо обойти все вершины дерева или ордерева не хаотично, а по определённому алгоритму.
Самые простые алгоритмы обхода для бинарного ордерева. Из 3 на выбор.
1)Прямой метод – обойти корень, затем левое поддерево, затем правое (КЛП)
Этот принцип соблюдается в любой момент времени.
2)Обратный метод: обойти левое поддерево, корень, правое поддерево (ЛКП)
3)Концевой метод: обойти левое поддерево, правое, корень (ЛПК)
Обойти 3 способам данное бинарное дерево (не менее 10 вершин)
1) Прямой (КЛП) a b d e f c g h I k
2) Обратный (ЛКП) d b f e a g c I h k
3) Концевой (ЛПК) d f e b g I k h c a
Для не бинарных деревьев и ордеревьев алгоритм гораздо сложнее.
Деревья и списки.
Бытовое понятие списков всем известно, но в информатике имеется формальное понятие списка.
Опр. Назовем атомом любой неделимый объект (букву, цифру и т.д.). Списками называется последовательность атомов и списков, разделенных запятыми и заключенными в общие скобки.
Это так называемая рекурсивное определение (использующие само себя). В математике это запрещается, а информатике широко применяется.
Примеры списков.
Атомы – буквы.
1. (а)
2. (a,b)
3. (a,b,c)
4. (a, (b,c))
5. ((a,b),c)
6. (a,((b,c),d),((e,f),g))
Каждому списку можно сопоставить ордерево, действуя по правилу
Атомом или списком, заключенным в общие скобки, соответствует общая безымянная вершина, потомками которой они являются.
Пример.
Видим, что атомам соответствуют только висячие вершины дерева. Поэтому обратная связь такова: каждому дереву соответствует список его висячих вершин.
Вводится понятие глубины списка: наибольшее число вложенных друг в друга скобок.
При этом глубина списка совпадает с глубиной соответствующего дерева (число уровней).
Поиск в дереве.
Проблема поиска в больших массивах информации – одна из важнейших в информатике.
Сразу ясно, что примитивный последовательный поиск очень долго и не эффективен.
Видим, что гораздо быстрее и эффективнее искать объекты, расположенные в виде бинарного дерева. Идя от корня мы на каждом шаге должны определить, влево или вправо надо двигаться. Например, можно наложить на вершины префиксный код (нули и единицы).
Чтобы сравнить длину последовательно поиска с поиском в бинарном дереве, выясним явязь количества вершин дерева с его глубиной. (Это и есть длина поиска). Для этого рассмотрим идеальное бинарное дерево, в котором каждая вершина (кроме висячих) имеет ровно 32 потомка – левый и правый.
Тогда вершин будет n=1+2+22+23+…+2k
S=2k+1=1
n=2k+1-1
2k+1=n+1
K+1=log2(n+1)
K=log2(n+1)-1
Пример. Пусти в идеальном бинарном ордереве миллион вершин. Какова длина поиска в таком дереве.
K=log210000000-1= 6log210-1=6*32=1+18,2=19 уровней.
Вопросы к экзамену по теме 3.
20. Что такое матрица смежности орграфа и какими свойством обладает матрица смежности неориентированного графа?
21. Как строиться код Харари.
22. Что называется деревом, ордеревом и как они связаны между собой?
23. Как строится префиксный код бинарного дерева?
24. Как строится код Прюфера
25. Какие 3 способа обхода бинарного дерева вы знаете (с примерами более 10 вершин)
26. Как связаны число вершин идеального бинарного дерева и его глубина?
27. Что называется атомом, списком и как связаны деревья со списком?
Задачи могут быть к вопросам 21-25, 27