Сбалансированное бинарное дерево в 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

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

Заключение

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

Счастливое обучение!