Деревья

Деревом (свободным) называется связный граф, не содержащий циклов. Произвольный граф, не содержащий циклов, называется ациклическим или лесом. Компонентами связности леса являются деревья. Дерево является частным случаем леса с единственной компонентой связности.

Примечание: прилагательное “свободное” подчеркивает отличие деревьев от других, родственных деревьям, объектов: ориентированных деревьев, упорядоченных деревьев и т.д.

В деревьях между количеством вершин и ребер справедливо следующее соотношение:

| X | = | U | + 1

где | X | - мощность множества вершин x_n,

| U | - мощность множества ребер u_m.

Т.е. у любого дерева число вершин на единицу больше числа его ребер.

Ориентированным деревом (или ордеревом, или корневым деревом) называется орграф со следующими свойствами:

· существует единственный узел, полустепень захода которого равна 0 (количество дуг, входящих в данную вершину). Он называется корнем ордерева;

· полустепень захода всех остальных узлов равна 1;

· каждый узел достижим из корня.

Ордерево обладает следующими свойствами:

1. m = n – 1;

2. если в ордереве отменить ориентацию ребер, то получится свободное дерево;

3. в ордереве нет контуров (циклов);

4. для каждого узла существует единственный путь, ведущий в этот узел из корня;

5. подграф, определяемый множеством узлов, достижимых из узла v, является ордеревом с корнем v (это ордерево называется поддеревом узла v);

6. если в свободном дереве любую вершину назначить корнем, то получится ордерево.

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

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

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

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

(Бинарное) дерево называется подровненным деревом, или АВЛ – деревом (Г.М.Адельсон-Вельский и Е.М.Ландис, 1962), или сбалансированным деревом, если для любого узла высота левого и правого поддеревьев отличается не более чем на 1.

Дата добавления: 2014-01-06