Pythonで二分探索木を実装する方法

2022.10.21
スポンサーリンク

今回は、2値探索木について学びます。

バイナリサーチツリーの背後にある基本的な概念を学習し、その後、コードを実装します。

この記事を読むには、バイナリツリーの概念に慣れている必要があります。

この記事もチェック：Pythonで再帰を使ってバイナリサーチを実装する方法

スポンサーリンク

バイナリサーチツリーとは？

バイナリサーチツリーは、バイナリツリーのデータ構造の一つで、バイナリツリーの特性とともに、さらなる特性を備えています。

  • 重複する値はありません。
  • ノードの左サブツリーは、それ自身のデータより小さいすべてのデータ値を持ちます。
  • ノードの右サブツリーは、それ自身のデータよりも大きなデータ値をすべて持っています。

これは次の例で見ることができる。

class BinaryTreeNode:
  def __init__(self, data):
    self.data = data
    self.leftChild = None
    self.rightChild=None

この記事もチェック：Pythonでバイナリツリーのノードを削除する方法

Pythonによるバイナリサーチツリーの実装

二分木を実装するために、二分木と同じノード構造を使用します。

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
 
root= insert(None,15)
insert(root,10)
insert(root,25)
insert(root,6)
insert(root,14)
insert(root,20)
insert(root,60)
a1=root
a2=a1.leftChild
a3=a1.rightChild
a4=a2.leftChild
a5=a2.rightChild
a6=a3.leftChild
a7=a3.rightChild
print("Root Node is:")
print(a1.data)
print("left child of node is:")
print(a1.leftChild.data)
print("right child of node is:")
print(a1.rightChild.data)
print("Node is:")
print(a2.data)
print("left child of node is:")
print(a2.leftChild.data)
print("right child of node is:")
print(a2.rightChild.data)
print("Node is:")
print(a3.data)
print("left child of node is:")
print(a3.leftChild.data)
print("right child of node is:")
print(a3.rightChild.data)
print("Node is:")
print(a4.data)
print("left child of node is:")
print(a4.leftChild)
print("right child of node is:")
print(a4.rightChild)
print("Node is:")
print(a5.data)
print("left child of node is:")
print(a5.leftChild)
print("right child of node is:")
print(a5.rightChild)
print("Node is:")
print(a6.data)
print("left child of node is:")
print(a6.leftChild)
print("right child of node is:")
print(a6.rightChild)
print("Node is:")
print(a7.data)
print("left child of node is:")
print(a7.leftChild)
print("right child of node is:")
print(a7.rightChild)

次に、2分木を実装するために、2分木に値を挿入する関数、2分木内の値を検索する関数、そして2分木から最小値と最大値を求める関数を実装します。

この記事もチェック：Pythonで最大公約数(HCF)と最小公倍数(LCM)をforとifで実装する方法

バイナリサーチツリーへのノードの挿入

バイナリサーチツリーにノードを挿入するとき、3つの条件が発生することがある。

  1. バイナリ探索木が空です。すなわち、ルート自身が値Noneになる。
  2. 挿入する値がルートより小さい。
    1. 挿入する値がルートより大きい。

1番目の条件を実現するには、新しいノードを作り、それをrootと宣言すればよい。

2番目と3番目の条件を実現するために、次のようなアプローチをとる。

二分探索木の性質から、各サブツリーはそれ自体が二分探索木であることがわかる。

したがって、各ノードを別の二分木のルートとして考えることができる。

新しいノードを挿入するとき、新しいデータの値が現在のノードの値より小さければ、二分探索木の左の子に追加し、そうでなければ、右の子に追加することになります。

再帰的に進めると、必ず最初の条件に到達するので、新しいノードを宣言し、そのノードをバイナリサーチツリーに追加します。

以下は、上記の手法の実装です。

Root Node is:
15
left child of node is:
10
right child of node is:
25
Node is:
10
left child of node is:
6
right child of node is:
14
Node is:
25
left child of node is:
20
right child of node is:
60
Node is:
6
left child of node is:
None
right child of node is:
None
Node is:
14
left child of node is:
None
right child of node is:
None
Node is:
20
left child of node is:
None
right child of node is:
None
Node is:
60
left child of node is:
None
right child of node is:
None

出力。

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 search(root,value):
    #Condition 1
    if root==None:
        return False
    #Condition 2
    elif root.data==value:
        return True
    #Condition 3
    elif root.data <value:
        return search(root.rightChild,value)
    # Condition 4
    else:
        return search(root.leftChild,value)
root= insert(None,15)
insert(root,10)
insert(root,25)
insert(root,6)
insert(root,14)
insert(root,20)
insert(root,60)
print(search(root,14))
print(search(root,22))

上の出力では、この例の二分探索木のすべての特性を確認することができます。

ここでは、ルートノードを宣言した後、そこにどのような要素の挿入順序があっても、出力は常に同じになります。

このコードをあなたのPython IDEにコピー＆ペーストして試してみてください。

この記事もチェック：Pythonによる線形探索の実装をコードを交えて分かりやすく解説する

二項探索木の要素を探索する

上記で、現在のノードの値より小さい値を持つノードは常に現在のノードの左サブツリーにあり、現在のノードの値より大きい値を持つノードは常に現在のノードの右サブツリーにあることを見てきました。

この性質を利用して、二項探索木の要素を探索することにします。

  1. カレントノードが空、すなわちNoneになった場合、検索する要素はツリー内に存在しないので、Falseを返す。
    1. 現在のノードが検索クエリと等しい値を持つ場合，True を返す。
    1. 検索する値が現在のノードの値より大きい場合、現在のノードの右側のサブツリーを検索します。
    1. 検索する値がカレントノードの値より小さい場合、カレントノードの左側サブツリーを検索します。

このロジックの実装を以下に示す。

True
False

結果は以下の通りです。

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 findLargestElement(root):
    #check if binary search tree is empty
    if root==None:
        return False
    #check if current node is rightmost node
    elif root.rightChild==None:
        return root.data
    #check right subtree of current node
    else:
        return findLargestElement(root.rightChild)
root= insert(None,15)
insert(root,10)
insert(root,25)
insert(root,6)
insert(root,14)
insert(root,20)
insert(root,60)
print("Largest Element is:")
print(findLargestElement(root))

How to find the maximum element of a Binary Search Tree?

これまで見てきたことから、現在のノードより大きな要素は常にその右側にあることが分かっています。

ルートから始まって最後まで再帰的に各ノードの右の子へ移動するとき、最大要素は最後に存在することになります。

つまり、二分探索木の最大の要素を見つけるには、木の一番右の要素を見つければよいのです。

このロジックの実装を以下に示す。

Largest Element is:
60

を結果を出力すると、以下の様になります。

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 findSmallestElement(root):
    #check if binary search tree is empty
    if root==None:
        return False
    #check if current node is leftmost node
    elif root.leftChild==None:
        return root.data
    #check right subtree of current node
    else:
        return findSmallestElement(root.leftChild)
root= insert(None,15)
insert(root,10)
insert(root,25)
insert(root,6)
insert(root,14)
insert(root,20)
insert(root,60)
print("Smallest Element is:")
print(findSmallestElement(root))

How to find smallest element of binary search tree?

現在のノードより小さい要素は、常にその左側にあることが分かっています。

ルートから始まって最後まで再帰的に各ノードの左の子に移動するとき、 最小の要素は最後のノードに存在することになります。

つまり、二分探索木の最小要素を見つけるには、木の一番左の要素を見つければよいのです。

このロジックの実装を以下に示す。

Smallest Element is:
6

を結果を出力すると、以下の様になります。

Askpython31
Depiction of Binary Search Tree

まとめ

この記事では、バイナリサーチツリーの背後にある基本的な概念について見てきました。

また、二分探索木の挿入、検索、最大要素の検索、最小要素の検索など、さまざまな操作を実装しました。

ぜひ、コードを実装して遊んでみてください。

今後も有益なチュートリアルにご期待ください。

楽しい学習を。

この記事もチェック：Pythonでバイナリツリーの最大値を求める方法

スポンサーリンク
タイトルとURLをコピーしました