Найти высоту бинарного дерева

Сбалансированное бинарное дерево в Python

В этой статье мы будем изучать сбалансированные бинарные деревья, и мы постараемся реализовать программу в Python, чтобы определить, сбалансирован ли двоичное дерево или нет. Чтобы прочитать эту статью, вы должны быть знакомы с концепцией бинарных деревьев.

Что такое сбалансированное бинарное дерево?

Сбалансированное бинарное дерево определяется как бинарное дерево, в котором на каждом узле его левое поддерево и правое судно имеет равную высоту или их высоту отличаться всего на 1.

Другими словами, если мы рассмотрим любой узел дерева в качестве корня дерева, то высоты его левого подмаревки и правого подмаревки никогда не должны отличаться более чем на 1.

Как проверить, является ли бинарное дерево сбалансировано или нет?

Согласно определению высота левого поддерева и правого поддерева не должна превышать одного на любом узле.

Поэтому, если мы рассмотрим дерево, которое будет сбалансировано на любом узле, нам придется найти высоту его левого подделка и правого подмаревки.

Тогда мы проверим разницу в высотах. Если разница выйдет больше 1 на любом узле, мы объявим, что дерево не сбалансировано. Ниже приведен алгоритм для этой процедуры:

Algorithm CheckBalancedBinaryTree: Input: Root Node of the binary tree. Output:True if binary tree is balanced and False otherwise. Start. 0.If tree is empty, return True. 1. Check the height of left sub-tree. 2.Check the height of right sub-tree. 3.If difference in height is greater than 1 return False. 4.Check if left sub-tree is balanced. 5.Check if right sub-tree is balanced. 6. If left sub-tree is balanced and right sub-tree is also balanced, return True. End

Мы выяснили алгоритм для проверки, если бинарное дерево сбалансировано, но мы не знаем, как рассчитать высоту дерева и подделки. Таким образом, мы сначала реализуем программу, чтобы найти высоту дерева, если узел корневого узла, а затем мы реализуем вышеуказанный алгоритм.

Как найти высоту сбалансированного бинарного дерева?

Чтобы найти высоту бинарного дерева, мы можем просто помнить следующие пункты.

• Если корень пуст, то высота дерева будет 0.
• Если root не пустой, то высота дерева будет равна максимальной высоте левого подделка корневого и правого подделка корня, добавленного 1.

Имея в виду вышеуказанные точки, алгоритм нахождения высоты дерева:

• Высота алгоритма (дерево):
• Вход: root дерева
• Выход: высота дерева
• Начинать.
• 1. Если корень нет, возврат 0.
• 2.Нажмите высоту левого подделки .//Height(root.leftChild)
• 3.Вы высота правого поддерева .//Height(root.rightChild)
• 4.Видите максимальное значение в 2 и 3 и добавьте 1 к нему.
• Конец

Теперь мы реализуем вышеуказанный алгоритм и выполните его для следующего бинарного дерева.

Программа найти высоту бинарного дерева

Ниже приведен код для поиска высоты бинарного дерева.

class BinaryTreeNode: def __init__(self, data): self.data = data self.leftChild = None self.rightChild=None def insert(root,newValue): #if binary search tree is empty, make a new node and declare it as root if root is None: root=BinaryTreeNode(newValue) return root #binary search tree is not empty, so we will insert it into the tree #if newValue is less than value of data in root, add it to left subtree and proceed recursively if newValuehright: return hleft+1 else: return hright+1 root= insert(None,15) insert(root,10) insert(root,25) insert(root,6) insert(root,14) insert(root,20) insert(root,60) print("Printing the height of the binary tree.") print(height(root)) 

Output: Printing the height of the binary tree. 3

Теперь мы знаем, как найти высоту бинарного дерева. Таким образом, мы теперь будем реализовать алгоритм, чтобы проверить, является ли двоичное дерево сбалансировано или не для указанного выше двоичного дерева.

Программа для проверки, если бинарное дерево сбалансировано или нет

Следующая программа была реализована для проверки, если бинарное дерево сбалансировано или нет.

class BinaryTreeNode: def __init__(self, data): self.data = data self.leftChild = None self.rightChild=None def insert(root,newValue): #if binary search tree is empty, make a new node and declare it as root if root is None: root=BinaryTreeNode(newValue) return root #binary search tree is not empty, so we will insert it into the tree #if newValue is less than value of data in root, add it to left subtree and proceed recursively if newValuehright: return hleft+1 else: return hright+1 def CheckBalancedBinaryTree(root): #if tree is empty,return True if root==None: return True #check height of left subtree lheight= height(root.leftChild) rheight = height(root.rightChild) #if difference in height is greater than 1, return False if(abs(lheight-rheight)>1): return False #check if left subtree is balanced lcheck=CheckBalancedBinaryTree(root.leftChild) #check if right subtree is balanced rcheck=CheckBalancedBinaryTree(root.rightChild) #if both subtree are balanced, return True if lcheck==True and rcheck==True: return True root= insert(None,15) insert(root,10) insert(root,25) insert(root,6) insert(root,14) insert(root,20) insert(root,60) print("Printing True if binary tree is balanced:") print(CheckBalancedBinaryTree(root)) 

Output: Printing True if binary tree is balanced: True

Поскольку бинарное дерево в нашем примере сбалансировано, программа напечатала правда. Вы можете проверить его для несбалансированных бинарных деревьев, изменяя программу для вставки новых значений.

Заключение

В этой статье мы изучали концепцию сбалансированного бинарного дерева. Мы также обсудили алгоритмы нахождения высоты бинарного дерева и проверки, если бинарное дерево сбалансировано или нет. Оставайтесь настроиться на более информативные статьи.

Читайте ещё по теме:

Источник

Как найти высоту бинарного дерева ( поиска )

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

То есть алгоритм не привязан к значению ключей узлов рассматриваемого двоичного дерева.

➡ Так как значения ключей вершин дерева ни на что не влияют, то я буду оперировать анонимным бинарным деревом при рассмотрении алгоритма нахождения высоты двоичного дерева.

Рисунок — стандартное анонимное бинарное дерево ( поиска )

А что, собственно, понимают под высотой бинарного дерева?

Высота двоичного дерева — это количество ветвей между его корнем и наиболее глубоко расположенным листовым узлом ( этот лист лежит на самом нижнем уровне ). Связи между узлами дерева называют ветвями ( реже ребрами ).

Для анонимного двоичного дерева, представленного на рисунке выше, высота будет иметь такое представление ( с точки зрения ветвей ):

Рисунок — анонимное двоичное дерево с высотой, выраженной через ветви

Следовательно, рассматриваемое анонимное бинарное дерево ( поиска ) имеет высоту, равную $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

Источник