Это одна из классических задач для двоичного дерева.
Кстати, хочу заметить, что высота определяется одним и тем же алгоритмом независимо от того, является ли дерево поисковым или просто двоичным деревом.
То есть алгоритм не привязан к значению ключей узлов рассматриваемого двоичного дерева.
➡ Так как значения ключей вершин дерева ни на что не влияют, то я буду оперировать анонимным бинарным деревом при рассмотрении алгоритма нахождения высоты двоичного дерева.
Рисунок — стандартное анонимное бинарное дерево ( поиска )
А что, собственно, понимают под высотой бинарного дерева?
Высота двоичного дерева — это количество ветвей между его корнем и наиболее глубоко расположенным листовым узлом ( этот лист лежит на самом нижнем уровне ). Связи между узлами дерева называют ветвями ( реже ребрами ).
Для анонимного двоичного дерева, представленного на рисунке выше, высота будет иметь такое представление ( с точки зрения ветвей ):
Рисунок — анонимное двоичное дерево с высотой, выраженной через ветви
Следовательно, рассматриваемое анонимное бинарное дерево ( поиска ) имеет высоту, равную $4$:
Рисунок — анонимное бинарное дерево высотой $4$
💡 Но, лично мне, крайне интересно понять, а чему, например, будет равна высота пустого двоичного дерева, или дерева, в котором только одна вершина! Эти моменты крайне важно понимать при анализе алгоритма, так как они являются своего рода пограничными.
Если бинарное поисковое дерево пустое, то есть не содержит ни одного элемента, то принято его высоту считать равной $-1$:
Если бинарное дерево состоит только из одной вершины, то по определению высота такого дерева равна $0$. Некоторые новички в программировании и структурах данных ошибочно считают, что такое дерево имеет высоту, равную $1$. Но это неправильно. Только $0$.
Рисунок — бинарное дерево высоты $0$
Хочу подытожить некоторую информацию относительно высоты бинарного дерева:
| # | Количество вершин в двоичном дереве | Как рассчитывается высота дерева |
| $1$ | $0$ ( пустое дерево ) | $-1$ |
| $2$ | $1$ | $0$ |
| $3$ | $>1$ | по формуле |
➡ Очевидно, что моя задача понять, по какой формуле следует рассчитывать высоту заданного двоичного дерева.
Учитывая, что древовидные структуры крайне удобно обрабатывать рекурсивно, то я буду мыслить в сторону рекурсивной обработки.
В результате долгих размышлений и анализа у меня получилась следующая рекурсивная функция ( каскадная рекурсия ):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
//------------------------------------------------------------------------------ // нахождение высоты двоичного дерева ( поиска ) // node - указатель на текущий узел дерева // в качестве ответа функция возвращает высоту текущего дерева // -1 - дерево пустое; // 0 - в дереве всего один элемент; // >0 - в дереве > 1 узла //------------------------------------------------------------------------------ int Height( const Node* const node ) { // высота левого поддерева относительно корня node int left_subtree_height; // высота правого поддерева относительно корня node int right_subtree_height; // хранит результат работы функции Height int max; // если текущего узла не существует, то высота дерева, для которого этот // узел является корнем, равна -1 if ( node == NULL ) { return -1; } // рекурсивно вычисляется высота левого поддерева, для которого node является корнем left_subtree_height = Height( node -> left ); // рекурсивно вычисляется высота правого поддерева, для которого node является корнем right_subtree_height = Height( node -> right ); // находим наибольшую высоту среди левого и правого поддеревьев if ( left_subtree_height > right_subtree_height ) { max = left_subtree_height; } else { max = right_subtree_height; } // в качестве результата возвращаем высоту дерева, для которого узел node является корнем return max + 1; } //------------------------------------------------------------------------------ |
➡ Подобные реализации я всегда отношу к разряду сложных, так как «за кулисами» работы рекурсии скрыто куча важнейших мелочей. Правильно и быстро программировать такие функции — достаточно сложная задача, требующая высокой квалификации программиста.
А сейчас я распишу логику этого алгоритма в табличной форме, чтобы улучшить читателям понимание принципа работы рекурсивной функции Height().
Для этого мне потребуется рассмотреть не анонимное двоичное дерево, а «нормальное», у которого узлы имеют конкретные значения ключей. Например, я хочу рассмотреть такое двоичное дерево поиска ( ключами выступают целые числа ):
Рисунок — двоичное дерево поиска ( «красный» путь показывает высоту дерева )
Анализирую логику алгоритма вычисления высоты двоичного дерева в табличной форме ( в данном случае эта форма наиболее наглядная и понятная ):
| # | Ключ | Формула | Высота |
| $1$ | $100$ | max( Height( $50$ ), Height( $150$ ) ) + $1$ | $?$ |
| $2$ | $50$ | max( Height( $25$ ), Height( $75$ ) ) + $1$ | $?$ |
| $3$ | $150$ | max( Height( $125$ ), Height( $200$ ) ) + $1$ | $?$ |
| $4$ | $25$ | лист | $0$ |
| $5$ | $75$ | max( Height( $63$ ), Height( $87$ ) ) + $1$ | $?$ |
| $6$ | $125$ | лист | $0$ |
| $7$ | $200$ | max( Height( $190$ ), Height( NULL ) ) + $1$ | $?$ |
| $8$ | $63$ | лист | $0$ |
| $9$ | $87$ | max( Height( NULL ), Height( $90$ ) ) + $1$ | $?$ |
| $10$ | $190$ | лист | $0$ |
| $11$ | $90$ | лист | $0$ |
Сейчас я буду подниматься снизу вверх по этой таблице, подставляя известные значения в формулы. Ответ, который меня интересует, будет получен в самой верхней строке таблицы. Я выделю это значение красным цветом.
➡ Напомню, что высота несуществующего двоичного дерева составляет $-1$, то есть Height( NULL ) = $-1$.
| # | Ключ | Формула | Высота |
| $1$ | $100$ | max( Height( $50$ ), Height( $150$ ) ) + $1$ | $4$ |
| $2$ | $50$ | max( Height( $25$ ), Height( $75$ ) ) + $1$ | $3$ |
| $3$ | $150$ | max( Height( $125$ ), Height( $200$ ) ) + $1$ | $2$ |
| $4$ | $25$ | лист | $0$ |
| $5$ | $75$ | max( Height( $63$ ), Height( $87$ ) ) + $1$ | $2$ |
| $6$ | $125$ | лист | $0$ |
| $7$ | $200$ | max( Height( $190$ ), Height( NULL ) ) + $1$ | $1$ |
| $8$ | $63$ | лист | $0$ |
| $9$ | $87$ | max( Height( NULL ), Height( $90$ ) ) + $1$ | $1$ |
| $10$ | $190$ | лист | $0$ |
| $11$ | $90$ | лист | $0$ |
В итоге хочу продемонстрировать бинарное дерево, у которого для каждой вершины проставлена соответствующая высота:
Рисунок — бинарное дерево с простановкой высот для каждой вершины
Еще хотелось бы пояснить за вычислительную сложность рассмотренного алгоритма. Очевидно, что в процессе вычисления высоты дерева приходится обойти каждый его узел, следовательно, вычислительная сложность составляет $O( n )$, где $n$ — количество вершин дерева.
Существуют ли более эффективные алгоритмы, чем $O( n )$? Возможно, но я таких не знаю 😎
Пишите в комментариях, все ли понятно по алгоритму нахождения высоты бинарного дерева, а также рассказываете, в каких случаях на практике вам потребовалось определять высоту дерева.
| ВНИМАНИЕ | Для заказа программы на двоичное дерево ( поиска ) пишите на мой электронный адрес proglabs@mail.ru |
Добавить комментарий