Пример 3.2

На рис.3.2: цепь, соединяющая вершину s с вершиной w, является ветвью; высота дерева (T, s) h (T) = 4; для вершины v вершина t – предок, вершина u – отец, а вершина w – сын; вершины r, w являются листьями; вершины r и u принадлежат одному ярусу.

Бинарное ориентированное дерево.

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

Утверждение 3.5. Пусть B - полное бинарное дерево высоты h, тогда оно имеет ровно 2^h листьев.

Доказательство проведем индукцией по высоте дерева h.

1. Если высота дерева h = 0, то оно имеет единственную вершину, которая является и корнем, и листом, т.е. 2⁰ = 1. Поскольку в бинарном полном ордереве полустепень исхода любой вершины за исключением листьев равна 2, то число листьев ордерева с высотой h = 1 будет равно 2⁰ × 2 = 2¹.

2. Пусть утверждение 3.5. справедливо для бинарного полного ордерева c высотой равной h – 1, т.е. число его листьев равно 2^h-1.

3. Тогда дерево B высоты h имеет 2^h-1 ×2 = 2^h листьев.

Утверждение 3.5. доказано.

Теорема 3.1 о высоте бинарного ориентированного дерева с заданным числом листьев. Бинарное ориентированное дерево с q листьями имеет высоту, не меньшую чем log₂ q.

Доказательство. Пусть рассматриваемое бинарное дерево имеет высоту h. Достроим его до бинарного полного дерева. Согласно утверждению 3.5 оно имеет 2^h листьев. Тогда для числа листьев исходного бинарного дерева справедливо неравенство q ≤ 2^h. Следовательно, log₂ q ≤ h.

Результат доказанной теоремы имеет важное значение в оценке сложности алгоритмов (см. раздел 3.3).

Дата добавления: 2015-07-20