こんにちはヤク学長です。
データサイエンティスト兼ファーマシストで、アルゴリズムやBI開発を行っています。
本記事の目的は、「アルゴリズムの基本を知る」ことを目的としています。
【本記事のもくじ】
下記の方法で、簡単に概要を抑えることができます。
- １．スタックとは
- ２．キューとは
それでは、上から順番に見ていきます。
なお、本上記の方法を順番に抑えれば成果が出ます。
記事の内容は「転載 & 引用OK」問題ありません。
１．Binary Serarch treeとは
Binary Search Tree（二分探索木）は、木構造を用いたデータ構造の1つです。二分探索木は、左部分木のすべての要素が右部分木の要素よりも小さく、右部分木のすべての要素が左部分木の要素よりも大きいという条件を満たす二分木です。これにより、検索や挿入、削除の操作をO(log n)で実現できます。
例えば、以下のような二分探索木があるとします。
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13この二分探索木に対して、要素7を検索する場合は、以下のように木をたどっていきます。
- 根ノードから探す値（7）を比較する。
- 7は8よりも小さいので、左部分木に移動する。
- 左部分木の根ノードは3であり、7は3よりも大きいので、右部分木に移動する。
- 右部分木の根ノードは6であり、7は6よりも大きいので、さらに右部分木に移動する。
- 右部分木の葉ノードに到達したため、探索を終了する。
以上のように、二分探索木では検索や挿入、削除において、操作する範囲を狭めながら木をたどっていくことで、O(log n)で効率的に操作を行うことができます。
Binary Serarch treeのInsert
Binary Search Tree に値を挿入する場合、以下の手順を行います。
- 挿入する値がルートノードである場合、そのノードをルートとします。
- 挿入する値が現在のノードの値よりも小さい場合、左の子ノードに挿入します。
- 挿入する値が現在のノードの値よりも大きい場合、右の子ノードに挿入します。
- 左または右の子ノードが存在しない場合、新しいノードをその場所に作成し、挿入する値をそのノードに格納します。
以下は、Python で Binary Search Tree に値を挿入する例です。
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, val):
if self.root is None:
self.root = Node(val)
return
current = self.root
while True:
if val < current.val:
if current.left is None:
current.left = Node(val)
break
else:
current = current.left
else:
if current.right is None:
current.right = Node(val)
break
else:
current = current.right
この例では、Node クラスが定義されています。このクラスは、Binary Search Tree のノードを表します。各ノードには値（val）、左の子ノード（left）、右の子ノード（right）が含まれます。
BST クラスは、Binary Search Tree を表します。このクラスには、ルートノード（root）が含まれます。insert メソッドは、新しい値を挿入するために使用されます。ルートノードが存在しない場合は、新しいノードをルートに設定します。存在する場合は、現在のノードをトラバースしながら、適切な位置に新しいノードを挿入します。
Binary Serarch treeのInoderとSearch
Binary Search Tree（二分探索木）における、Inorder traversal（中順走査）とSearch（探索）について説明します。
まず、Binary Search Treeとは、各ノードに対して、左部分木のすべての要素の値が自身より小さく、右部分木のすべての要素の値が自身以上であるような木構造を指します。このような性質を持つため、Binary Search Treeに格納されたデータは、探索を高速に行うことができます。
まず、Inorder traversalとは、二分探索木を中順走査することで、木の要素を小さい順から順に出力する方法です。具体的には、左部分木、自身のノード、右部分木の順に要素を出力します。以下は、Inorder traversalを行うためのPythonコードです。
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def inorderTraversal(root):
if root:
inorderTraversal(root.left)
print(root.val)
inorderTraversal(root.right)
次に、Searchとは、Binary Search Treeから特定の値を探索することです。Binary Search Treeは、探索対象の値が小さいか大きいかで探索方向を決定するため、探索範囲を劇的に減らすことができます。以下は、Searchを行うためのPythonコードです。
def search(root, key):
if root is None or root.val == key:
return root
if root.val < key:
return search(root.right, key)
return search(root.left, key)
これらの関数を使って、Binary Search Treeの探索、挿入、削除などの操作を行うことができます。
Binary Serarch treeのremove
Binary Search Treeにおいて、ノードを削除する場合のアルゴリズムは以下のようになります。
- 削除するノードが葉ノードの場合
削除するノードをそのまま削除します。
- 削除するノードが子を1つだけ持つ場合
削除するノードの親ノードと、その子ノードを繋ぎ変えます。
- 削除するノードが子を2つ持つ場合
削除するノードの次節点を、削除するノードの代わりに配置します。次節点とは、削除するノードの右の部分木の中で、最も小さい値を持つノードのことです。次節点を削除するノードの代わりに配置することで、削除するノードを削除しても、Binary Search Treeの性質が保たれます。
Pythonで実装した場合、以下のようになります。
def deleteNode(root, key):
if root is None:
return root
if key < root.key:
root.left = deleteNode(root.left, key)
elif key > root.key:
root.right = deleteNode(root.right, key)
else:
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
temp = minValueNode(root.right)
root.key = temp.key
root.right = deleteNode(root.right, temp.key)
return root
def minValueNode(node):
current = node
while(current.left is not None):
current = current.left
return current
削除対象のノードを探索し、上記の3つの場合分けに応じて削除処理を行っています。削除するノードが子を2つ持つ場合は、削除するノードの次節点を探索しています。
Binary Serarch treeをクラスで管理する
以下はPythonで実装されたBinary Search Treeのクラス例です。この例では、ノードが削除されるときには、右のサブツリーの最小値を見つけ、その値で削除されるノードを置き換える方法を採用しています。
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = Node(val)
else:
self._insert(val, self.root)
def _insert(self, val, node):
if val < node.val:
if node.left is None:
node.left = Node(val)
else:
self._insert(val, node.left)
elif val > node.val:
if node.right is None:
node.right = Node(val)
else:
self._insert(val, node.right)
def inorder(self):
if self.root is None:
return []
else:
return self._inorder(self.root)
def _inorder(self, node):
if node:
return self._inorder(node.left) + [node.val] + self._inorder(node.right)
else:
return []
def search(self, val):
if self.root is None:
return False
else:
return self._search(val, self.root)
def _search(self, val, node):
if val == node.val:
return True
elif val < node.val and node.left:
return self._search(val, node.left)
elif val > node.val and node.right:
return self._search(val, node.right)
return False
def remove(self, val):
if self.root is None:
return self.root
else:
self.root = self._remove(val, self.root)
def _remove(self, val, node):
if val < node.val:
node.left = self._remove(val, node.left)
elif val > node.val:
node.right = self._remove(val, node.right)
else:
if node.left is None:
temp = node.right
node = None
return temp
elif node.right is None:
temp = node.left
node = None
return temp
temp = self._minValueNode(node.right)
node.val = temp.val
node.right = self._remove(temp.val, node.right)
return node
def _minValueNode(self, node):
current = node
while current.left is not None:
current = current.left
return current
このクラスを使って、Binary Search Treeを以下のように作成できます。
bst = BST()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)
# inorder traversal of the BST
print(bst.inorder()) # [20, 30, 40, 50, 60, 70, 80]
# search for a node
print(bst.search(70)) # True
print(bst.search(100)) # False
# remove a node
bst.remove(20)
print(bst.inorder()) # [30, 40, 50, 60, 70, 80]Heapとは
Heap（ヒープ）とは、データを木構造で表現するデータ構造の一つで、完全二分木を基本的な形状として利用するものです。一般に、親の値が常に子の値以上（または以下）であるという性質を持ちます。この性質をヒープ条件と呼びます。
ヒープは主に二つの種類に分けられます。
- 最小ヒープ（Min Heap）：親の値が常に子の値以上であるヒープで、ルートに最小の値が入る。
- 最大ヒープ（Max Heap）：親の値が常に子の値以下であるヒープで、ルートに最大の値が入る。
主にヒープは、データの優先度付きキューを実装するために使用されます。また、ヒープソートという高速なソートアルゴリズムも存在します。
Heapの実装
Heapは、完全二分木を利用したデータ構造であり、最小値や最大値をO(log n)で取り出すことができます。Heapは通常、Priority Queueとして使用され、データをソートしたり、最小値や最大値のみを取り出すことが必要なアルゴリズムによく使用されます。
Heapの実装方法は、配列またはポインタを使用することができます。配列を使用する場合、二分木のノードを1次元配列に格納することができます。通常、ノードiの親はi/2、左の子は2i、右の子は2i+1で表されます。
以下は、配列を使用したMin Heapの実装例です。
class MinHeap:
def __init__(self):
self.heap = []
def insert(self, val):
self.heap.append(val)
self.heapify_up(len(self.heap) - 1)
def extract_min(self):
if not self.heap:
return None
min_val = self.heap[0]
last_val = self.heap.pop()
if self.heap:
self.heap[0] = last_val
self.heapify_down(0)
return min_val
def heapify_up(self, index):
parent = (index - 1) // 2
if parent >= 0 and self.heap[parent] > self.heap[index]:
self.heap[parent], self.heap[index] = self.heap[index], self.heap[parent]
self.heapify_up(parent)
def heapify_down(self, index):
left = 2 * index + 1
right = 2 * index + 2
smallest = index
if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
smallest = left
if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
smallest = right
if smallest != index:
self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
self.heapify_down(smallest)
この実装例では、Min Heapが実装されています。Min Heapは、各ノードの値がその子ノードの値よりも小さいことを保証するデータ構造です。ノードを挿入する場合、まず配列の最後にノードを追加し、その後、ノードを適切な場所に移動します。最小値を取り出す場合は、最小値を取り出して、最後のノードを根に移動して、ノードを適切な場所に移動する必要があります。
というわけで、今回は以上です。大変大変お疲れ様でした。
引き続きで、徐々に発信していきます。
コメントや感想を受け付けています。ちょっとした感想でもいいので嬉しいです。
それでは、以上です。
