Вопрос 7: Деревья и бинарные деревья. Их функциональная спецификация и логическое описание. Специфические способы физического представления деревьев.

Дерево -  это граф, не содержащий циклов, петель и кратных ребер.

 

С точки зрения программирования удобнее использовать рекурсивное определение дерева: деревом типа Т называется структура, которая образована данным типа Т, называемым корнем дерева, и конечным, возможно, пустым множеством с переменным числом элементов – деревьев типа Т, называемых поддеревьями этого дерева. Такое дерево в программировании принято называть сильно ветвящимся.

 

Напомним, что k-м уровнем в дереве называется множество вершин, каждую из которых отделяет от корня k ребер. Если вершина u k-го уровня смежна с вершиной v (k-1)-го уровня, то u - потомок v, а v - предок (отец) u. Вершины, имеющие одного и того же предка, называются братьями.

            Рис. 1.11. Дерево.

 

           

 

 

 

            Рис. 7.1. Дерево

            Пример. На рис. 1.11 вершина A - предок для вершин B, C, D; вершина G -потомок для вершины D, вершины E и F - братья, т.к. у них общий предок B.

            Более подробную информацию о деревьях и их свойствах см. в курсе дискретной математики, например, в [7].

            Так как дерево - это частный случай графа, то для физического представления деревьев годятся все четыре способа представления графов. Кроме того, для деревьев существуют специфические способы задания. Эти способы учитывают свойства деревьев и позволяют снизить затраты памяти и время доступа к информации о вершинах по сравнению со стандартными способами представления графов. Познакомимся с двумя из таких способов.

 

I способ

            Простейший и наиболее наглядный способ представления дерева заключается в следующем: для каждой вершины в памяти ЭВМ хранится

            - информация о самой вершине (например, ее имя) или ссылка на информацию о ней;

            - ссылки на каждого из потомков.

            Пример. Дерево, изображенное на рис 1.11, I-м способом можно представить в виде семи списков так: PA®PB®PC®PD, PB®PE®PF, PC, PD®PG, PE, PF, PG. Здесь PV означает ссылку на вершину v.

II способ

            При этом способе хранения для каждой вершины в памяти ЭВМ хранится

            - информация о самой вершине (например, ее имя) или ссылка на информацию о ней;

            - ссылка на самого левого потомка;

            - ссылка на правого брата.

            Пример. Дерево, изображенное на рис 1.11, II-м способом можно представить так: (PA,PB,nil), (PB,PE,PC), (PC,nil,PD), (PD,PG,nil), (PE,nil,PF), (PF,nil,nil) (PG,nil,nil). Здесь PV означает ссылку на вершину v.

 

 

Бинарное (двоичное) дерево (ДДТ) типа Т - это структура данных, которая либо пуста, либо состоит из корня и двух непересекающихся бинарных деревьев, называемых левым (ЛПД) и правым (ППД) поддеревьями данного дерева.

            На первый взгляд кажется, что бинарное дерево является частным случаем  сильно ветвящегося дерева, из каждой вершины которого всегда выходит не более двух ветвей. Однако это не так. Главное различие состоит в том, что два возможных поддерева ДДТ

                                               

                                                             

                                                                                                         

 

 

существенно различаются, тогда как в  обычных  деревьях они были бы идентичны и оба соответствовали бы схеме

                                                          

 

 

 

            Кроме того, ДДТ может быть пусто, а обычное дерево – нет. На рис. 1.12 прдставлены примеры бинарных деревьев.

     Рис. 1.12. Примеры бинарных деревьев.

 

            Функциональная спецификация двоичного дерева включает операции:

доступ:           дерево_пусто - операция проверяет, является ли дерево пустым;

                        чтение_корня - получение корня непустого дерева;

                        слева - доступ к ЛПД непустого дерева;

                        справа - доступ к ППД непустого дерева;

модификация:

                        добавление вершины;

                        удаление вершины;

                        построение - составление дерева из заданных корня, ЛПД и ППД. Операцию “построение” можно также рассматривать, как создание дерева.

 

Логическое описание

            Естественное логическое описание состоит в рассмотрении бинарного дерева как соединение корня (элемента типа Т) и двух поддеревьев ЛПД и ППД.

тип ДДТ = (ПУСТО или НЕ_ПУСТОЕ_ДДТ);

тип НЕ_ПУСТОЕ_ДДТ = (корень:Т, ЛПД, ППД: ДДТ).

 

Физическое представление

            Чтобы представить двоичное дерево цепным способом, каждый элемент списка должен содержать, как минимум, три поля: информация о вершине и два указателя - к ЛПД и ППД.

            Пример. Бинарными являются деревья, описывающие родословную некоторого человека. При этом левый указатель PМ хранит адрес информации о матери, а правый указатель PО - адрес информации об отце:

(Я,PМ,PО)

(Мать,PМ,PО)  (Отец,PМ,PО)

(БабушкаМ,PМ,PО) (ДедушкаМ,PМ,PО)       (БабушкаО,PМ,PО) (ДедушкаО,PМ,PО)

...

            На некотором уровне информация о родственниках безвозвратно утеряна.

            В некоторых случаях бинарное дерево удобно хранить в виде массива М, т.е. использовать не цепное, а сплошное представление дерева. При таком способе хранения  М[1] - это элемент в корне дерева, а М[2i] и М[2i+1] - элементы в левом и правом потомках той вершины, в которой хранится элемент М[i].

            Пример. Для дерева, изображенного на рис. 1.12,г массив М выглядит следующим образом:            М[1]=A;

                                               М[2*1]=М[2]=B;                   М[2*1+1]= М[3]=C;

                                               М[2*2]=М[4]=D;                   М[2*2+1]= М[5]=E;

                                               М[2*3]=М[6]=F;                   М[2*3+1]= М[7]=G.

            Из приведенного выше примера хорошо видно, что в массиве М вершины (k-1)-го уровня стоят раньше вершин k-го уровня, а вершины одного уровня расположены в порядке слева направо.

            К сожалению, не каждое двоичное дерево можно хранить таким способом.

            Пример. Для дерева, изображенного на рис. 1.12,в в массиве М имеются “дыры”:  М[1]=A;

                        М[2*1]=М[2]=B;                   М[2*1+1]= М[3]=C;

                        М[2*2]=М[4]=?;                    М[2*2+1]= М[5]=?;

                        М[2*3]=М[6]=C.

            Количество ребер в самой “длинной” ветке дерева определяет его высоту.

            Пример. Дерево на рис. 1.12,а имеет высоту 2, дерево на рис. 1.12,б - высоту 1. Сплошной способ хранения годится, например, для бинарного дерева фиксированной высоты с максимальным количеством вершин. На рис. 1.12,б представлено такое дерево высотой 1, а на рис. 1.12,г - высотой 2.