二分探索木 （Pythonによるアルゴリズムとデータ構造）
本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。
今回は、二分探索木（Binary Search Tree）について学んでいきます。
二分探索木とは
前回の「基本的なデータ構造」においては二分木について学びました。
二分探索木（Binary Search Tree）とは、この二分木の特性を利用し、以下の条件を追加したものを言います。
- ある節xにおいて、左部分木の要素はxより小さい
- ある節xにおいて、右部分木の要素はxより大きい
この条件をもとに探索をした場合、左部分木を辿っていけば、その木の最小の要素に辿り着き、また右部分木を辿っていけば、その木の最大の要素に辿り着くことができます。
また計算量に関して、二分探索木では根から探索を開始し、もし木が完全二分木（Complete Binary Tree）であれば、O(log n)の計算量で済みます。
完全二分木とは節の数が2^n - 1であるとき、つまり以下のような状態です。
しかし、データを登録する順序がたまたま昇順（もしくは降順）であった場合、以下のような木構造となってしまいます。
これでは、単なる線形探索になってしまうため、最悪はO(n) の計算量となります。
Pythonで二分探索木を実装してみる
それでは、Pythonで二分探索木を実装してみます。
# binary_search_tree.py
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self, key):
self.root = Node(key)
def search(self, key):
node = self.root
while node:
if node.key == key:
print("Found!")
return node
elif node.key > key:
node = node.left
else:
node = node.right
return None
def insert(self, key):
node = self.root
while node:
parent = node
if node.key == key:
print("Data already exists.")
return
elif node.key > key:
node = node.left
flag = "left"
else:
node = node.right
flag = "right"
new = Node(key)
if flag == "left":
parent.left = new
else:
parent.right = new
def deletemin(self, node):
parent = node
tmp = node.right
while tmp.left:
parent = tmp
tmp = tmp.left
parent.right = tmp.right
return tmp
def delete(self, key):
node = self.root
parent = node
flag = None
while node:
if node.key == key:
if node.left == None and node.right == None:
if flag == "left":
parent.left = None
else:
parent.right = None
elif node.left == None:
if flag == "left":
parent.left = node.right
else:
parent.right = node.right
elif node.right == None:
if flag == "left":
parent.left = node.left
else:
parent.right = node.left
else:
tmp = self.deletemin(node)
if flag == "left":
parent.left = tmp
else:
parent.right = tmp
tmp.right = node.right
tmp.left = node.left
parent = node
if node.key > key:
node = node.left
flag = "left"
else:
node = node.right
flag = "right"
def inorder(self, tree):
tmp = tree
if tmp == None:
return
else:
self.inorder(tmp.left)
print(tmp.key)
self.inorder(tmp.right)
t = BinarySearchTree(4)
t.insert(2)
t.insert(1)
t.insert(3)
t.insert(6)
t.insert(5)
t.insert(7)
print("delete 6")
t.delete(6)
print("print data...")
t.inorder(t.root)
基本的な探索は簡単で、
- キーが節のキーと同じであるか
- キーが節のキーより大きいか
- キーが節のキーより小さいか
について条件分岐させていきます。
挿入に関しては、節とキーの値を比較し、節がない状態まで左右の部分木を辿ります。
節がない場所がわかれば、そこが正しい挿入場所となるので、あとは挿入するだけとなります。
削除に関しては少し複雑になり、
- 節が子を持たない
- 節が一つの子を持っている
- 節が二つの子を持っている
の3つに条件分岐させ処理をします。
また前回の二分木の通りがけ順で木をなぞれば、昇順で表示させることができます。
動作確認
それでは上記で作成したスクリプトを実行してみます。
> python binary_search_tree.py insert 1 to 7. print data... 1 2 3 4 5 6 7 delete 6 print data... 1 2 3 4 5 7
今回は上記のfig1のような完全二分木を作成します。
1から7までを挿入した後に木の状態を確認し、さらに6を削除した後に再度木の状態を確認しています。
参考書籍
定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)
