Overview
二分探索木（Binary Search Tree, BST） は、要素を動的に管理しながら、高速な検索・追加・削除ができるデータ構造。「BST の基本概念」から「バランス木」までを理解していく。
1.二分探索木（BST）とは？
2.二分探索木の基本操作
3.平衡二分探索木（Balanced BST）
4.典型問題を解いてみる
1. 二分探索木（BST）とは？
BST の基本ルール
1. 左部分木のすべての値は、親ノードより小さい
2. 右部分木のすべての値は、親ノードより大きい
3. 各ノードの部分木もまた BST である（再帰的構造）
(1) 二分探索木の例
10
/ \
5 15
/ \ / \
3 7 12 18
-
10 の左側（5, 3, 7）は 10 より小さい
-
10 の右側（15, 12, 18）は 10 より大きい
-
部分木（5 の下の 3, 7 など）も BST のルールを満たしている
-
BST のメリット
O(log N) の計算量で検索・追加・削除が可能
要素を動的に追加・削除しても木の構造が維持される
順番付きデータの管理に便利 -
BST のデメリット
「偏った木」になると O(N) の計算量になる
バランスを保つ工夫が必要（→ AVL 木、赤黒木などの平衡木を学ぶ）
2. 二分探索木の基本操作
(1) 挿入（Insert）
BST に要素を挿入する際：
1. ルートから開始し、挿入位置を決定
2. 小さければ左、大きければ右へ移動
3. 空いているノードの位置に新しいノードを追加
<実装>
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
# 使用例
root = None
root = insert(root, 10)
root = insert(root, 5)
root = insert(root, 15)
- 計算量: 平均 O(log N)、最悪 O(N)（偏った木の場合）
(2) 探索（Search）
BST では、探索も O(log N) で可能。
def search(root, key):
if root is None or root.key == key:
return root
if key < root.key:
return search(root.left, key)
return search(root.right, key)
# 使用例
result = search(root, 15)
print(result.key if result else "Not found")
- 計算量: O(log N)（最悪 O(N)）
(3) 削除（Delete）
削除には 3 パターンがある：
1. 葉ノード（子なし）の削除 → そのまま削除
2. 子が 1 つのノードの削除 → 子を親に直接つなぐ
3. 子が 2 つのノードの削除 → 中序順で次の要素（右部分木の最小値）に置き換える
<実装>
def min_value_node(node):
current = node
while current.left is not None:
current = current.left
return current
def delete(root, key):
if root is None:
return root
if key < root.key:
root.left = delete(root.left, key)
elif key > root.key:
root.right = delete(root.right, key)
else:
# ケース 1 & 2: 子なし or 子 1 つ
if root.left is None:
return root.right
elif root.right is None:
return root.left
# ケース 3: 子が 2 つ
temp = min_value_node(root.right) # 右部分木の最小値
root.key = temp.key
root.right = delete(root.right, temp.key)
return root
- 計算量: O(log N)（最悪 O(N)）
3. 平衡二分探索木（Balanced BST）
BST は、木のバランスが崩れると最悪 O(N) になる。
そこで、「平衡木」 を使って O(log N) を維持する ことが重要。
(1) 代表的な平衡木
-
AVL 木
各ノードの高さの差を最大 1 に保つ
回転（Rotations）を使ってバランスを保つ
-
赤黒木（Red-Black Tree）
挿入・削除時に色を使ってバランスを保つ
Python の set や dict に内部的に使われる
4. 典型問題を解いてみる
例題1. BST の挿入
問題: N 個の整数を BST に挿入し、順番に出力せよ。
回答
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
N = int(input())
values = list(map(int, input().split()))
root = None
for v in values:
root = insert(root, v)
print(root.key) # ルートを出力
例題2. BST の探索
問題: BST に X が含まれているか判定せよ。
回答
def search(root, key):
if root is None or root.key == key:
return True if root else False
return search(root.left, key) if key < root.key else search(root.right, key)
X = int(input())
print("Yes" if search(root, X) else "No")