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 に挿入し、順番に出力せよ。

参考： ABC315 B - Insert 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 が含まれているか判定せよ。

参考： ABC318 B - Search BST

回答　

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")