二分探索木 (BST)
このトピックを修了すると
二分探索木の基本的なルールを説明でき、挿入と探索をコードで実装でき、中位巡回によってソートされたデータを取得できます。
配列の限界
ソートされた配列での二分探索は O(log n) で高速です。しかし、挿入と削除は遅いです。なぜなら、途中に値を挿入するには、残りの要素をずらさなければならないからです。
[2, 5, 8, 12, 15]
↑ ここに 7 を挿入するには
[2, 5, 7, 8, 12, 15] ← 8, 12, 15 を右にずらさなければならない (O(n))検索も高速で、挿入も高速なデータ構造が必要です。それが二分探索木です。
基本的なルール
二分探索木 (Binary Search Tree, BST) は、たった 1 つのルールを守ります。
左の子 < 親 < 右の子
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13どのノードを見ても、左部分木のすべての値はそれよりも小さく、右部分木のすべての値はそれよりも大きくなります。
ノードの実装
class Node: def __init__(self, value): self.value = value self.left = None self.right = None各ノードは、値 1 つと、左/右の子を指すポインタ 2 つを持ちます。
挿入
新しい値を挿入するとき、ルートから始めてルールに従って下っていきます。
def insert(root, value): if root is None: return Node(value) if value < root.value: root.left = insert(root.left, value) elif value > root.value: root.right = insert(root.right, value) return root# ツリーの作成root = Nonefor v in [8, 3, 10, 1, 6, 14, 4, 7, 13]: root = insert(root, v)値が現在のノードよりも小さい場合は左、大きい場合は右に進みます。空の場所を見つけたら、そこに新しいノードを作成します。
探索
def search(root, target): if root is None: return False if target == root.value: return True elif target < root.value: return search(root.left, target) else: return search(root.right, target)print(search(root, 7)) # Trueprint(search(root, 5)) # False二分探索と同じ原理です。各ステップで半分を破棄するため、バランスの取れたツリーでは O(log n) です。
探索の過程 (7 を探すとき):
8 → 7 < 8, 左
3 → 7 > 3, 右
6 → 7 > 6, 右
7 → 見つかった！中位巡回 — ソートされた結果
ツリーを 「左 → 自分 → 右」 の順序で訪問すると、ソートされた順序で値を取得できます。これを 中位巡回 (in-order traversal) と呼びます。
def inorder(root): if root is None: return [] return inorder(root.left) + [root.value] + inorder(root.right)
print(inorder(root)) # [1, 3, 4, 6, 7, 8, 10, 13, 14]BST のルール (左 < 親 < 右) に従って左から訪問すると、自然に昇順になります。個別のソートアルゴリズムなしで、ソートされたデータを取得することになります。
3 つの巡回
def preorder(root): # 前位: 自分 → 左 → 右 if root is None: return [] return [root.value] + preorder(root.left) + preorder(root.right)
def postorder(root): # 後位: 左 → 右 → 自分 if root is None: return [] return postorder(root.left) + postorder(root.right) + [root.value]print(preorder(root)) # [8, 3, 1, 6, 4, 7, 10, 14, 13]print(inorder(root)) # [1, 3, 4, 6, 7, 8, 10, 13, 14]print(postorder(root)) # [1, 4, 7, 6, 3, 13, 14, 10, 8]| 巡回 | 順序 | 用途 |
|---|---|---|
| 前位 (preorder) | 自分 → 左 → 右 | ツリーのコピー、シリアライズ |
| 中位 (inorder) | 左 → 自分 → 右 | ソートされた出力 |
| 後位 (postorder) | 左 → 右 → 自分 | ツリーの削除、数式ツリーの評価 |
最悪の場合
BST のパフォーマンスは、ツリーのバランスによって決まります。
# バランスの取れたツリー (O(log n)) # 偏ったツリー (O(n)) — 実際には連結リスト
8 1
/ \ \
3 10 2
/ \ \ \
1 6 14 3
\
4ソートされたデータを順番に挿入すると、偏ったツリーになります。この問題を解決するために、AVL 木や Red-Black 木などの自己平衡ツリーがあります。Python の sorted()、Java の TreeMap の内部で、このような平衡ツリーを使用します。
時間計算量のまとめ
| 演算 | 平均 | 最悪 (偏り) |
|---|---|---|
| 探索 | O(log n) | O(n) |
| 挿入 | O(log n) | O(n) |
| 削除 | O(log n) | O(n) |
| 巡回 | O(n) | O(n) |
BST の削除 — 3 つのケース
削除は、BST で最も複雑な演算です。
def delete(root, value): if root is None: return None if value < root.value: root.left = delete(root.left, value) elif value > root.value: root.right = delete(root.right, value) else: # ケース 1: 子がない (リーフ) — 単に削除 if root.left is None and root.right is None: return None # ケース 2: 子が 1 つ — 子がその場所を置き換え elif root.left is None: return root.right elif root.right is None: return root.left # ケース 3: 子が 2 つ — 後続ノードで置き換え else: successor = find_min(root.right) root.value = successor.value root.right = delete(root.right, successor.value) return root
def find_min(node): while node.left: node = node.left return node子ノードが 2 つあるノードを削除する場合、右部分木の最小値 (中位後続ノード) で置き換えます。BST のソート条件が維持されます。
実務で BST を直接使うか
Python には BST の組み込みモジュールはありません。代わりに:
from bisect import insort, bisect_left
sorted_list = []insort(sorted_list, 5) # ソートを維持しながら挿入insort(sorted_list, 3)insort(sorted_list, 7)print(sorted_list) # [3, 5, 7]
idx = bisect_left(sorted_list, 5) # 二分探索print(sorted_list[idx]) # 5bisect モジュールは、ソートされたリストで BST と同様の O(log n) 探索を提供します。挿入は O(n) (配列の移動) であるため、挿入が頻繁に行われる場合は、SortedContainers などのサードパーティライブラリを使用します。
BST vs ハッシュテーブル vs ソートされた配列
| 演算 | BST (バランス) | ハッシュテーブル | ソートされた配列 |
|---|---|---|---|
| 検索 | O(log n) | O(1) (平均) | O(log n) |
| 挿入 | O(log n) | O(1) (平均) | O(n) |
| 削除 | O(log n) | O(1) (平均) | O(n) |
| 最小/最大 | O(log n) | O(n) | O(1) |
| 範囲検索 | O(log n + k) | O(n) | O(log n + k) |
| ソートされた出力 | O(n) | O(n log n) | O(n) |
ハッシュテーブルは高速ですが、「ソートされた順序」が必要な場合は BST が有利です。たとえば、データベースのインデックスは、「100 以上 200 以下の値」のように範囲のクエリが必要な場合に BST が適しています。
BST は、「ソートされたデータを動的に維持」する必要がある場合に適しています。配列と連結リストの利点を組み合わせたデータ構造です。