Overview
二分探索木（Binary Search Tree, BST） は、順序付きデータを動的に管理するための基本データ構造。
検索・挿入・削除を平均 O(log N) で実行でき、基礎として必須知識。
1.二分探索木（BST）とは？
2.二分探索木の基本操作
3.平衡二分探索木（Balanced BST）
4.Python で BST を実装しない理由（重要）
5.典型問題を解いてみる
1. 二分探索木（BST）とは？
BST（Binary Search Tree）のルール
1. 左部分木の値は親より小さい
2. 右部分木の値は親より大きい
3. 部分木も再帰的に BST
10
/ \
5 15
/ \ / \
3 7 12 18
BST のメリット
- 検索・挿入・削除が 平均 O(log N)
- 順序付きデータの管理に強い
- 中順（inorder）走査するとソート済みの列が得られる
BST のデメリット
- 「偏った木」になると O(N) の計算量になる
→ 次章の「平衡二分探索木（AVL / 赤黒木）が重要になる」
2. 二分探索木の基本操作
(1) ノード定義
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
(2) 挿入（Insert）
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
- 計算量: 平均 $O(log N)$、最悪 $O(N)$（偏った木の場合）
(3) 探索（Search）
def search(root, key):
if root is None or root.key == key:
return root is not None
return search(root.left, key) if key < root.key else search(root.right, key)
(4) 削除（Delete）
削除には 3 パターンがある：
1. 葉ノード（子なし）の削除 → そのまま削除
2. 子が 1 つのノードの削除 → 子を親に直接つなぐ
3. 子が 2 つのノードの削除 → 中序順で次の要素（右部分木の最小値）に置き換える
def min_value_node(node):
current = node
while current.left:
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:
# 子が0 or 1
if root.left is None:
return root.right
elif root.right is None:
return root.left
# 子が2つ
temp = min_value_node(root.right)
root.key = temp.key
root.right = delete(root.right, temp.key)
return root
3. 平衡二分探索木（Balanced BST）
BST は偏ると O(N) になるため、現代ではほとんど**平衡木（Balanced BST）**が使われる。
代表的な平衡木
- AVL Tree：高さ差を最大 1 に維持
- Red-Black Tree（赤黒木）
→ C++ のset/map、JavaのTreeMapに使われている
→ Python のdict/setは赤黒木ではなくハッシュテーブル
4. Python で BST を実装しない理由（重要）
Pythonには標準でBSTが存在しない。
理由：
| 用途 | Python の実装 |
|---|---|
| 高速検索 | → dict/set（ハッシュテーブル） |
| 優先度付き | → heapq（ヒープ） |
| 順序付き集合 | → bisect（ソートリスト＋二分探索） |
つまり：
PythonではBSTの用途はbisectやheapで十分代替可能
アルゴリズム・CS の理解のために BST を学ぶ意味は大きいが、Pythonの実務ではほとんど使わない。
5. 典型問題を解いてみる
例題1. BST の挿入
問題: 整数列を 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. 中順（Inorder）走査でソートされた配列を出力
問題: BST に N 個の数値を挿入し、ソート済みの順序で出力せよ。
回答
def inorder(root, res):
if root:
inorder(root.left, res)
res.append(root.key)
inorder(root.right, res)
N = int(input())
A = list(map(int, input().split()))
root = None
for x in A:
root = insert(root, x)
res = []
inorder(root, res)
print(*res)
例題3.二分探索木の最近共通祖先（LCA）
問題：BST 上の 2 ノードの LCA（Lowest Common Ancestor）を求めよ。
回答
def lca(root, a, b):
if root is None:
return None
if a < root.key and b < root.key:
return lca(root.left, a, b)
if a > root.key and b > root.key:
return lca(root.right, a, b)
return root.key # このノードが分岐点
例題4.Python の bisect を使って「BST 風の問題」を解く
棒を切りながら、区間長を求める有名問題。
本質は 順序付き集合（Balanced BST）。
Python では bisect で代替。
回答
import bisect
L, Q = map(int, input().split())
cuts = [0, L]
for _ in range(Q):
c, x = map(int, input().split())
if c == 1:
bisect.insort(cuts, x)
else:
i = bisect.bisect_left(cuts, x)
print(cuts[i] - cuts[i - 1])
例題5.K番目に小さい値（Order Statistics）
※ C++ なら policy-based data structure（木構造）
※ Python はソートリスト＋bisect で代替
回答
import bisect
N, Q = map(int, input().split())
A = []
for _ in range(N):
x = int(input())
bisect.insort(A, x)
for _ in range(Q):
k = int(input())
print(A[k-1])