Вычисление высоты бинарного дерева

Определение 5.5. Неориентированным деревом называют связный и ациклический неориентированный граф.

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

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

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

Определение 5.7. Вершину v ориентированного дерева называют потомком (подлинным потомком) вершины [math]u[/math], если существует путь из [math]u[/math] в [math]{v}[/math] (путь ненулевой длины из [math]u[/math] в [math]{v}[/math]). В этом же случае вершину [math]u[/math] называют предком (подлинным предком) вершины [math]{v}[/math], а если длина пути из [math]u[/math] в [math]{v}[/math] равна 1, то вершину [math]{v}[/math] называют сыном вершины [math]u[/math], которая при этом вполне естественно именуется отцом вершины [math]{v}[/math]. Вершину, не имеющую потомков, называют листом.

На рис. 5.14 вершины [math]v_4[/math] и [math]v_5[/math] есть сыновья вершины [math]v_2[/math], которая, в свою очередь, является сыном вершины [math]v_0[/math] — корня дерева. Вершины [math]v_4[/math] и [math]v_5[/math] являются подлинными потомками вершин [math]v_0[/math] и [math]v_2[/math], которые соответственно будут их подлинными предками. Вершины [math]v_1, v_4, v_5, v_6,v_9, v_8[/math] — листья дерева. Взаимно недостижимые вершины ориентированного дерева (например, такие, как [math]v_2[/math] и [math]v_9[/math]) не являются ни предком, ни потомком одна другой. Каждая вершина будет сама для себя предком и потомком, но не подлинным.

Определение 5.8. Произвольный ациклический граф называют неориентированным лесом. Бели каждая слабая компонента ориентированного графа является ориентированным деревом, то такой граф называют ориентированным лесом.

На рис. 5.15, а даны примеры неориентированного леса, а на рис. 5.15, б — примеры ориентированного леса.

Определение 5.9. Подграф неориентированного (ориентированного) дерева, являющийся неориентированным (ориентированным) деревом, называют поддеревом исходного дерева.

Из определения следует, что неориентированный лес — это неориентированный граф, каждая компонента которого является неориентированным деревом.

На рис. 5.14 подграф, порожденный множеством вершин [math]{v_3,v_6,v_7,v_8,v_9}[/math], является поддеревом изображенного на рисунке ориентированного дерева.

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

На рис. 5.13 граф, изображенный слева, является кустом. Рассмотрим теперь некоторые числовые параметры, которыми характеризуется ориентированное дерево.

Определение 5.11. Высота ориентированного дерева — это наибольшая длина пути из корня в лист; глубина [math]d(v)[/math] вершины ориентированного дерева [math]{v}[/math] — это длина пути из корня в эту вершину; высота [math]h(v)[/math] вершины ориентированного дерева [math]{v}[/math] — это наибольшая длина пути из данной вершины в лист и, наконец, уровень вершины ориентированного дерева — это разность между высотой ориентированного дерева и глубиной данной вершины.

Уровень корня равен высоте ориентированного дерева, но уровни различных листьев, так же как и их глубины, могут быть различными; высота любого листа равна нулю (см. рис. 5.14).

Определение 5.12. Ориентированное дерево называют бинарным, если полустепень исхода любой его вершины не больше 2; бинарное ориентированное дерево называют полным, если из любой его вершины, не являющейся листом, исходят ровно две дуги, а уровни всех листьев совпадают.

Примеры различных бинарных ориентированных деревьев приведены на рис. 5.16: ориентированные деревья на рис. 5.16, (а и б) неполные, а ориентированное дерево на рис. 5.16,в полное.

Используя индукцию по высоте ориентированного дерева, можно показать, что в полном бинарном ориентированном дереве высоты [math]h[/math] ровно [math]2^h[/math] листьев. Действительно, ориентированное дерево высоты 0 имеет [math]2^0=1[/math] лист. Полное бинарное ориентированное дерево высоты 1 имеет [math]2^1=2[/math] листа.

Пусть полное бинарное ориентированное дерево имеет высоту [math]k[/math] и соответственно [math]2^k[/math] листьев. Рассмотрим полное бинарное ориентированное дерево высоты [math]k+1[/math]. Поскольку в полном бинарном ориентированном дереве уровни всех листьев совпадают, легко видеть, что ориентированное дерево высоты [math]k+1[/math] можно получить из полного бинарного ориентированного дерева высоты [math]k[/math], если из каждого листа последнего провести по две дуги. Тогда количество листьев в ориентированном дереве высоты [math]k+1[/math] будет в 2 раза больше, чем в ориентированном дереве высоты [math]k[/math], то есть [math]2^kcdot2=2^{k+1}[/math].

Отсюда следует, что в произвольном бинарном дереве высоты [math]h[/math] не более [math]2^h[/math] листьев. Таким образом, мы получаем следующий простой, но важный результат.

Теорема о высоте бинарного ориентированного дерева

Теорема 5.2 (теорема о высоте бинарного ориентированного дерева с заданным числом листьев). Бинарное ориентированное дерево с [math]n[/math] листьями имеет высоту, не меньшую [math]log_{2}n[/math].

Эта теорема имеет одно весьма интересное приложение. Предположим, что необходимо расположить строго по возрастанию элементы конечного линейно упорядоченного множества [math]{a_1,ldots,a_n}[/math]. Эту задачу называют задачей сортировки, а любой алгоритм, ее решающий, — алгоритмом сортировки. С математической точки зрения алгоритм сортировки должен найти такую перестановку [math]{a_{i_1},ldots,a_{i_n}}[/math] элементов множества, которая была бы согласована с заданным на нем отношением [math]leqslant[/math] линейного порядка, т.е. для любых [math]k,l[/math] из справедливости неравенства [math]i_k