Высота двоичного дерева в C/C++
Высота бинарного дерева определяется как максимальная глубина любого конечного узла от корневого узла. То есть это длина самого длинного пути от корневого узла до любого конечного узла.
Давайте рассмотрим приведенное ниже двоичное дерево.
Поскольку листовые узлы, соответствующие максимальной глубине, равны 40 и 50, чтобы найти высоту, мы просто находим количество ребер от корневого узла до любого из этих двух узлов, что равно 3.
Теперь, когда мы знаем, что означает высота бинарного дерева, мы построим алгоритм для нахождения высоты любого бинарного дерева.
Логика для нахождения высоты двоичного дерева в C++
Давайте теперь решим логику определения высоты и сначала напишем наш псевдокод.
Мы будем использовать рекурсию по дереву, чтобы найти высоту. (Концепции см. в статье Википедии)
Поскольку высота дерева определяется как наибольший путь от корня до листа, мы можем рекурсивно вычислить высоту левого и правого поддеревьев.
Теперь мы можем применить определение высоты к поддеревьям.
Мы наблюдаем, что это максимум между левым и правым поддеревьями, а затем добавляем единицу.
Поскольку высота дерева равна максимальной высоте поддерева + 1, мы продолжаем делать это, пока поддерево не станет NULL , а его высота равна 0.
В этот момент наша функция окончательно завершится, и
Давайте напишем функцию tree_height() , которая вычисляет высоту.
// Find height of a tree, defined by the root node int tree_height(Node* root) < if (root == NULL) return 0; else < // Find the height of left, right subtrees left_height = tree_height(root->left); right_height = tree_height(root->right); // Find max(subtree_height) + 1 to get the height of the tree return max(left_height, right_height) + 1; > Строка №3 оценивает условие завершения, когда размер поддерева равен 0 или когда корневой узел имеет значение NULL .
Строки 7 и 8 рекурсивно находят высоту левого и правого поддеревьев.
И, наконец, строка 11 возвращает максимальное значение из двух, возвращая высоту дерева.
Реализация на С/С++
Ниже приведена полная программа, показывающая, как строится двоичное дерево, а затем показана логика определения высоты в tree_height() .
#include #include typedef struct Node Node; // Define the Tree Node here struct Node < int value; // Pointers to the left and right children Node* left, *right; >; Node* init_tree(int data) < // Creates the tree and returns the // root node Node* root = (Node*) malloc (sizeof(Node)); root->left = root->right = NULL; root->value = data; return root; > Node* create_node(int data) < // Creates a new node Node* node = (Node*) malloc (sizeof(Node)); node->value = data; node->left = node->right = NULL; return node; > void free_tree(Node* root) < // Deallocates memory corresponding // to every node in the tree. Node* temp = root; if (!temp) return; free_tree(temp->left); free_tree(temp->right); if (!temp->left && !temp->right) < free(temp); return; >> int tree_height(Node* root) < // Get the height of the tree if (!root) return 0; else < // Find the height of both subtrees // and use the larger one int left_height = tree_height(root->left); int right_height = tree_height(root->right); if (left_height >= right_height) return left_height + 1; else return right_height + 1; > > int main() < // Program to demonstrate finding the height of a Binary Tree // Create the root node having a value of 10 Node* root = init_tree(10); // Insert nodes onto the tree root->left = create_node(20); root->right = create_node(30); root->left->left = create_node(40); root->left->right = create_node(50); // Find the height of the tree int height = tree_height(root); printf("Height of the Binary Tree: %d\n", height); // Free the tree! free_tree(root); return 0; > Все права защищены. © Linux-Console.net • 2019-2023
Источник
Как найти высоту бинарного дерева ( поиска )
Кстати, хочу заметить, что высота определяется одним и тем же алгоритмом независимо от того, является ли дерево поисковым или просто двоичным деревом.
То есть алгоритм не привязан к значению ключей узлов рассматриваемого двоичного дерева.
➡ Так как значения ключей вершин дерева ни на что не влияют, то я буду оперировать анонимным бинарным деревом при рассмотрении алгоритма нахождения высоты двоичного дерева.
Рисунок — стандартное анонимное бинарное дерево ( поиска )
А что, собственно, понимают под высотой бинарного дерева?
Высота двоичного дерева — это количество ветвей между его корнем и наиболее глубоко расположенным листовым узлом ( этот лист лежит на самом нижнем уровне ). Связи между узлами дерева называют ветвями ( реже ребрами ).
Для анонимного двоичного дерева, представленного на рисунке выше, высота будет иметь такое представление ( с точки зрения ветвей ):
Рисунок — анонимное двоичное дерево с высотой, выраженной через ветви
Следовательно, рассматриваемое анонимное бинарное дерево ( поиска ) имеет высоту, равную $4$:
Рисунок — анонимное бинарное дерево высотой $4$
💡 Но, лично мне, крайне интересно понять, а чему, например, будет равна высота пустого двоичного дерева, или дерева, в котором только одна вершина! Эти моменты крайне важно понимать при анализе алгоритма, так как они являются своего рода пограничными.
Если бинарное поисковое дерево пустое, то есть не содержит ни одного элемента, то принято его высоту считать равной $-1$:
Если бинарное дерево состоит только из одной вершины, то по определению высота такого дерева равна $0$. Некоторые новички в программировании и структурах данных ошибочно считают, что такое дерево имеет высоту, равную $1$. Но это неправильно. Только $0$.
Рисунок — бинарное дерево высоты $0$
Хочу подытожить некоторую информацию относительно высоты бинарного дерева:
| # | Количество вершин в двоичном дереве | Как рассчитывается высота дерева |
| $1$ | $0$ ( пустое дерево ) | $-1$ |
| $2$ | $1$ | $0$ |
| $3$ | $>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 |
Источник
Деревья поиска
Дерево — одна из наиболее распространенных структур данных в программировании.
Деревья состоят из набора вершин (узлов, нод) и ориентированных рёбер (ссылок) между ними. Вершины связаны таким образом, что от какой-то одной вершины, называемой корневой (вершина 8 на рисунке), можно дойти до всех остальных единственным способом.
- Родитель вершины $v$ — вершина, из которой есть прямая ссылка в $v$.
- Дети (дочерние элементы, сын, дочь) вершины $v$ — вершины, в которые из $v$ есть прямая ссылка.
- Предки — родители родителей, их родители, и так далее.
- Потомки — дети детей, их дети, и так далее.
- Лист (терминальная вершина) — вершина, не имеющая детей.
- Поддерево — вершина дерева вместе со всеми её потомками.
- Степень вершины — количество её детей.
- Глубина вершины — расстояние от корня до неё.
- Высота дерева — максимальная из глубин всех вершин.
Деревья чаще всего представляются в памяти как динамически создаваемые структуры с явными указателями на своих детей, либо как элементы массива связанные отношениями, неявно определёнными их позициями в массиве.
Деревья также используются в контексте графов.
Бинарные деревья поиска
Бинарное дерево поиска (англ. binary search tree, BST) — дерево, для которого выполняются следующие свойства:
- У каждой вершины не более двух детей.
- Все вершины обладают ключами, на которых определена операция сравнения (например, целые числа или строки).
- У всех вершин левого поддерева вершины $v$ ключи не больше, чем ключ $v$.
- У всех вершин правого поддерева вершины $v$ ключи больше, чем ключ $v$.
- Оба поддерева — левое и правое — являются двоичными деревьями поиска.
Более общим понятием являются обычные (не бинарные) деревья поиска — в них количество детей может быть больше двух, и при этом в «более левых» поддеревьях ключи должны быть меньше, чем «более правых». Пока что мы сконцентрируемся только на двоичных, потому что они проще.
Чаще всего бинарные деревья поиска хранят в виде структур — по одной на каждую вершину — в которых записаны ссылки (возможно, пустые) на правого и левого сына, ключ и, возможно, какие-то дополнительные данные.
Как можно понять по названию, основное преимущество бинарных деревьев поиска в том, что в них можно легко производить поиск элементов:
Эта функция — как и многие другие основные, например, вставка или удаление элементов — работает в худшем случае за высоту дерева. Высота бинарного дерева в худшем случае может быть $O(n)$ («бамбук»), поэтому в эффективных реализациях поддерживаются некоторые инварианты, гарантирующую среднюю глубину вершины $O(\log n)$ и соответствующую стоимость основных операций. Такие деревья называются сбалансированными.
Источник