はじめに
「二分探索木」は、データの探索において重要なアルゴリズムの一つとして、プログラミングやデータサイエンスを学んでいる方にはおなじみのものと思います。
ですが初心者にとってはなかなか理解しづらく私も理解するのに時間がかかってしまいました。ここでは、実際にPythonで二分探索木を作るコードを入力し、イメージできるよう画像で表現することを試みました。
二分探索木の基本
二分木とは？
二分探索木は、各ノードが最大で2つの子ノードを持つ「二分木」と呼ばれる木構造を基にしています。
二分木では、左の子ノードよりも親が大きな値、右の子ノードは親よりも大きな値を持っています。
この特性により、データの検索や追加などが効率的に行えます。
二分探索木の作成
データ配列の要素順にデータを追加して二分探索木を作成します。二分木を辿りながら適切な位置にノードを挿入します。最初の要素を根に入れ、次の要素が根より大きいか小さいかで、根の左か右の子のノードへ挿入します。
これをPythonでプログラムを動かしながら、確かめてみたいと思います。
Pythonでの実装
Pythonで、二分探索木を実装します。以下は、ノードを挿入して二分探索木を作るコードです。
二分探索木では探索のほかに、データの追加、削除もできますが、ここでは二分探索木の作成を行ないます。探索と追加は基本的に同じ流れでおこなうことになります。
【初心者入門】どうすればPythonが使えるのか、インストール方法を解説 – ライフ＆ジョブブログ (life-and-job.com)
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def __str__(self):
left = f'[{self.left.value}]' if self.left else '[]'
right = f'[{self.right.value}]' if self.right else '[]'
return f'{left} <- {self.value} -> {right}'
class BinarySearchTree:
def __init__(self):
self.nodes = []
def add_node(self, value):
node = Node(value)
if self.nodes:
parent, direction = self.find_parent(value)
if direction == 'left':
parent.left = node
else:
parent.right = node
self.nodes.append(node)
def find_parent(self, value):
node = self.nodes[0]
while node:
p = node
if p.value == value:
raise ValueError('すでにある値と同じ値を格納することはできません')
if p.value > value:
direction = 'left'
node = p.left
else:
direction = 'right'
node = p.right
return p, directionここで、以下のような配列を作り、これを左側の要素から順に二分探索木を作成させます。以下のコードを入力して実行してみてください。
btree = BinarySearchTree()
for v in [10, 20, 12, 5, 3, 8, 30, 15, 7, 4, 11, 2, 9, 25, 35 ]:
btree.add_node(v)
for node in btree.nodes:
print(node)実行すると右のようになります。ちょっと分かりずらいですが、配列の要素順に、ノードとしてデータを追加していきます。
根は、10ですが、次の20は10より大きいので、10の右側の子となります。
次に12は、10より大きいのでやはり、右に行きますが、20がすでにいるために、20の子となります。20より小さいので左の子となります。
次の5は10より小さいので、10の左側の子となります。
これを順次行なっていき、すべて葉になった時点で終了します。
結果は下のような木構造になります。
検索は、この二分探索木の根から始まり、各ノードを比較して目的の値を持つノードを見つけるまで木をたどります。
追加は二分探索木の作成と同じ流れです。
削除については、コードにはしていませんが、以下のように行います。
１．子を持っていない場合は、そのまま削除
２．子を１つ持っている場合は、子のノードを削除する親ノードへ移動
３．子を２つ持っている場合は、削除する親ノードより左側のノードの中で最も大きい値を持つノードを削除する親ノードの位置へ移動します。
コードの解説
以下に、各クラスとメソッドの解説をわかりやすく記述します。
Node クラス
このクラスは、二分探索木の各ノードを表します。各ノードは値 (value)、左の子ノード (left)、右の子ノード (right) を持っています。
__init__(self, value): ノードを初期化します。与えられた値をノードの値として設定し、左右の子ノードを初期化します。__str__(self): ノードの文字列表現を返します。左の子ノード、ノードの値、右の子ノードを表示します。
BinarySearchTree クラス
このクラスは、二分探索木全体を管理します。ノードを追加する際には、追加先の親ノードを見つけるための find_parent メソッドが使われます。
__init__(self): 二分探索木を初期化します。ノードのリストnodesを用意します。add_node(self, value): 与えられた値を持つ新しいノードを追加します。find_parentメソッドを使用して、適切な位置にノードを配置します。find_parent(self, value): 与えられた値の親ノードを見つけます。木を辿りながら、与えられた値と比較して適切な位置を見つけます。見つかった親ノードと、左か右かの情報を返します。
二分探索木作成アニメーション
上述のコードで作成する探索木をアニメーション化してみました。配列順にノードができていない点はご容赦いただきたいと思いますが、イメージはつかんでいただけるかと思います。
まとめ
二分探索木は、その柔軟性と効率性からさまざまなアプリケーションで利用されるアルゴリズムですが、そのイメージをつかめるよう、Pythonでコードを実装し、画像で表現してみました。本当はプログラム上のノードの追加順にあわせてアニメーションも作りたかったのですが、ここは今後の課題です。
実際のコードで確認したり、イメージをつかむのに活用していただければ幸いです。
コメント