[Список тем] [Вступление к этой теме] [1] [2] [3]

Ориентированные, упорядоченные и бинарные деревья.

Ориентированные (упорядоченные) деревья являются абстракцией иерархических отношений, которые очень часто встречаются как в практической жизни, так и в математике и в программировании. Дерево (ориентированное) и иерархия - это равнообъемные понятия.

1. Ориентированные деревья

Определение

Ориентированным деревом (или ордеревом, или корневым деревом) называется орграф со следующими свойствами:
  1. существует единственный узел, полустепень захода которого равна 0. Он называется корнем ордерева;
  2. полу степень захода всех остальных узлов равна 1;
  3. каждый узел достижим из корня.
Пример
На рис. 5 приведены диаграммы всех различных ориентированных деревьев с 3 узлами, а на рис. 6 показаны диаграммы всех различных ориентированных деревьев с 4 узлами.

Pис. 5
Рис. 5. Ориентированные деревья с 3 узлами
Pис. 6
Рис. 6. Ориентированные деревья с 4 узлами

ТЕОРЕМА

Ордерево обладает следующими свойствами:
  1. q = p-1;
  2. если в ордереве отменить ориентацию ребер, то получится свободное дерево;
  3. в ордереве нет контуров;
  4. для каждого узла существует единственный путь, ведущий в этот узел из корня;
  5. подграф, определяемый множеством узлов, достижимых из узла v, является ордеревом с корнем v (это ордерево называется поддеревом узла v);
  6. если в свободном дереве любую вершину назначить корнем, то получится ордерево.

доказательство

  1. Каждое ребро входит в какой-то узел. Из п. 3 определения 1 имеем:

v V\{u} d+(v) = 1,
следовательно, q = p - 1.
2. Пусть G - ордерево, граф G' получен из G отменой ориентации ребер, u - корень.
Тогда v1 v2 V <v1, u> G' & <u, v2> G', следовательно, v1, v2 <v1, v2> и граф G' связен. Таким образом, учитывая п. 4. теоремы 2, G' - дерево.
3. Следует из 2.
4. От противного. Если бы в G существовали два пути из u в v, то в G' имелся бы цикл.
5. Пусть Gv - правильный подграф, определяемый множеством узлов, достижимых из v. Тогда d+Gv (v) = 0, иначе узел v был бы достижим из какого-то узла v' Gv и, таким образом, в Gv, а значит, и в G имелся бы контур, что противоречит 3. Далее имеем: v'Gv\{v}d+(v')=1, так как Gv G. Все вершины Gv достижимы из v по построению. По определению получаем, что Gv - ордерево.
6. Пусть вершина и назначена корнем и дуги последовательно ориентированы "от корня" обходом в глубину. Тогда d+(u) = 0 по построению; v V\{u} d+(v) = 1, так как входящая дуга появляется при первом посещении узла; все узлы достижимы из корня, так как обход в глубину посещает все вершины связного графа. Таким образом, по определению получаем ордерево.

ЗАМЕЧАНИЕ

Каждое свободное дерево определяет не более р ориентированных деревьев. Таким образом, общее число различных ордеревьев с р узлами не более чем в р раз превосходит общее число различных свободных деревьев с р вершинами.

Определения

Концевая вершина ордерева называется листом. Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой. Уровень узла ордерева - это расстояние от корня до узла. Сам корень имеет уровень 0. Узлы одного уровня образуют ярус дерева.

ЗАМЕЧАНИЕ

Наряду с "растительной" применяется еще и "генеалогическая" терминология. Узлы, достижимые из узла u, называются потомками узла u (потомки образуют поддерево). Если в дереве существует дуга (u, v), то узел u называется отцом (или родителем) узла v, a узел v называется сыном узла u. Сыновья одного узла называются братьями.

2. Эквивалентное определение ордерева

Ордерево Т - это конечное множество узлов, таких что:
1. имеется один узел r, называемый корнем данного дерева;
2. остальные узлы (исключая корень) содержатся в k попарно непересекающихся " множествах T1, ..., Tk, каждое из которых является ордеревом (k >= 0).
T={{r}, T1, ...,Tk}.

3. Упорядоченные деревья

Множества Т1, ..., Tk в экивалентном определении ордерева являются поддеревьями. Если относительный порядок поддеревьев T1, ..., Tk фиксирован, то ордерево называется упорядоченным.
Пример
Ориентированные и упорядоченные ориентированные деревья интенсивно используются в программировании.
1. Выражения. Для представления выражений языков программирования, как правило, используются ориентированные упорядоченные деревья. Пример представления выражения a + b * с показан на рис. 7 слева.
2. Для представления блочной структуры программы и связанной с ней структуры областей определения идентификаторов часто используется ориентированное дерево (может быть, неупорядоченное, так как порядок определения переменных в блоке в большинстве языков программирования считается несущественным). На рис. 7 в центре показана структура областей определения идентификаторов а, b, с, d, e, причем для отображения структуры дерева использована альтернативная техника.
3. Для представления иерархической структуры вложенности элементов данных и/или операторов управления часто используется техника отступов, показанная на рис. 7 справа.

Pис. 7
Рис. 7. Примеры изображения деревьев в программировании

4. Структура вложенности каталогов и файлов в современных операционных системах является упорядоченным ориентированным деревом.

ОТСТУПЛЕНИЕ

Это отражается даже в терминологии - "корневой каталог диска".

5. Различные "уравновешенные скобочные структуры" (например (o(b)(c(d)(e)))) являются ориентированными упорядоченными деревьями.

ЗАМЕЧАНИЕ

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

Пример
На рис. 8 приведены три диаграммы деревьев, которые внешне выглядят различными. Обозначим дерево слева - (1), в центре - (2) и справа - (3). Как упорядоченные деревья, они все различны: (1) (2), (2) (3), (3) (1). Как ориентированные деревья (1) = (2), но (2) (3). Как свободные деревья, они все изоморфны: (1) = (2) = (3).

 
Рис. 8. Диаграммы деревьев

4. Бинарные деревья

Определение

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

Пример
На рис. 9 приведены две диаграммы деревьев, которые изоморфны как упорядоченные, ориентированные и свободные деревья, но не изоморфны как бинарные деревья.

Pис. 9
Рис. 9. Два различных бинарных дерева

[Список тем] [Вступление к этой теме] [1] [2] [3]