今回は、バランスのとれた二分木について勉強し、二分木がバランスしているかどうかを判断するプログラムをPythonで実装してみる。
この記事を読むには、2分木の概念に慣れている必要があります。
バランス型バイナリツリーとは？
バランス2分木とは、すべてのノードにおいて、左の部分木と右の部分木の高さが等しいか、または高さが1だけ異なる2分木のことです。
言い換えれば、木の任意のノードを木の根と考えた場合、その左の部分木と右の部分木の高さが1以上異なることはないはずです。
この記事もチェック：Pythonでバイナリツリーのノードを削除する方法
How to check if a Binary Tree is Balanced or not?
定義によると、どのノードでも左サブツリーと右サブツリーの高さは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になる。
- ルートが空でない場合、木の高さはルートの左の部分木とルートの右の部分木の最大高さに1を足したものになります。
以上の点を考慮し、木の高さを求めるアルゴリズムは以下の通りです。
- Algorithm height(tree):
- 入力。入力：木の根っこ
- 出力 出力：木の高さ
- Start.
- 1.ルートがNoneの場合、0を返す。
- 2.左のサブツリーの高さを求める.//height(root.leftChild)
- 3.右のサブツリーの高さを求める.//height(root.rightChild)
- 4.2と3の最大値を求め、それに1を足す。
- 終了
では、上記のアルゴリズムを実装し、以下の2分木に対して実行します。
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 newValue<root.data:
root.leftChild=insert(root.leftChild,newValue)
else:
#if newValue is greater than value of data in root, add it to right subtree and proceed recursively
root.rightChild=insert(root.rightChild,newValue)
return root
def height(root):
#if root is None return 0
if root==None:
return 0
#find height of left subtree
hleft=height(root.leftChild)
#find the height of right subtree
hright=height(root.rightChild)
#find max of hleft and hright, add 1 to it and return the value
if hleft>hright:
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))
|
二分木の高さを求めるプログラム
以下は、2分木の高さを求めるコードです。
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 newValue<root.data:
root.leftChild=insert(root.leftChild,newValue)
else:
#if newValue is greater than value of data in root, add it to right subtree and proceed recursively
root.rightChild=insert(root.rightChild,newValue)
return root
def height(root):
#if root is None return 0
if root==None:
return 0
#find height of left subtree
hleft=height(root.leftChild)
#find the height of right subtree
hright=height(root.rightChild)
#find max of hleft and hright, add 1 to it and return the value
if hleft>hright:
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))
|
さて、二分木の高さを求める方法はわかった。
そこで、上記の2分木に対して、2分木が釣り合っているかどうかを調べる アルゴリズムを実装してみる。
バイナリーツリーがバランスしているかどうかをチェックするプログラム
以下のプログラムは、2分木がバランスしているかどうかを確認するために実装されています。
Output:Printing True if binary tree is balanced:
True |
この例の二分木はバランスがとれているので、プログラムはTrueを出力している。
このプログラムを修正して、新しい値を挿入することにより、アンバランスな2分木をチェックすることができる。
まとめ
この記事では、バランスのとれた二分木の概念について学びました。
また、2分木の高さを求めるアルゴリズムと、2分木が釣り合うかどうかをチェックするアルゴリズムについても説明しました。
今後も有益な記事を期待しています。
それでは、よいお年を