ВУЗ:
Составители:
Рубрика:
называется корнем дерева;
2. полуступень всех остальных узлов равна 1;
3. каждый узел достижим из корня.
На рис. 27 приведены диаграммы всех различных ориентированных деревьев с 4
узлами.
Бинарное дерево – это конечное множество узлов, которое либо пусто, либо состоит
из корня и двух непересекающихся бинарных деревьев – левого и правого. Бинарное
дерево не является упорядоченным
деревом. На рис. 28 приведены две диаграммы
деревьев, которые изоморфны как упорядоченные, ориентированные и свободные
деревья, но не изоморфны как бинарные деревья.
Ордерево называется выровненным, если все узлы, степень которых меньше 2,
располагаются на одном или двух последних уровнях. На рис. 29 приведены диаграммы
выровненного (слева) и невыровненного (справа) деревьев.
(Бинарное) дерево
называется подровненным деревом, или АВЛ-деревом
(Адельсон-Вельский и Ландис), или сбалансированным деревом, если для любого узла
высота левого и правого поддеревьев отличается не более чем на 1. на рис. 30 приведена
диаграмма максимально несимметричного сбалансированного дерева, в котором для всех
узлов высота левого поддерева ровно на 1 больше высоты правого поддерева.
Рис. 27
Рис. 29
