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

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

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

1. существует единственный узел, полустепень захода которого равна 0. Он на­зывается корнем ордерева;

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

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

Пример

На рис. 7.3 приведены диаграммы всех различных ориентированных деревьев с 3 узлами, а на рис. 7.4 показаны диаграммы всех различных ориентированных деревьев с 4 узлами.

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

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

ТЕОРЕМА Ордерево обладает следующими свойствами:

1. q = p – 1;

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

3.в ордереве нет контуров;

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

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

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

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

Множества Т ₁ ,..., T_k в эквивалентном определении ордерева являются поддере­вьями. Если относительный порядок поддеревьев T ₁,..., T_k фиксирован, то ордерево называется упорядоченным.

Пример

Ориентированные и упорядоченные ориентированные деревья интенсивно ис­пользуются в программировании. Выражения для представления выражений языков программирования, как правило, используются ориентированные упорядоченные деревья.

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

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

Бинарное дерево не является упорядоченным ордеревом.

Пример

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

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

Выровненные деревья

Ордерево называется выровненным, если все узлы, степень которых меньше 1 располагаются на одном или двух последних уровнях. Выровненное дерево имеет наименьшую возможную для данного р высоту h.

Пример

На рис. 7.6 приведены диаграммы выровненного (слева) и невыровненне: (справа) деревьев.

Рис. 7.6. Выровненное (слева) и невыровненное деревья

Сбалансированные деревья

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

Пример

На рис. 7.7 приведена диаграмма максимально несимметричного сбалансиро­ванного дерева, в котором для всех узлов высота левого поддерева ровно на 1 больше высоты правого поддерева.

Рис. 7.7. Сбалансированное дерево

Дата добавления: 2014-12-27