《アルゴリズムを学ぶ》20.２分探索木

# Overview
二分探索木（Binary Search Tree, BST） は、要素を動的に管理しながら、高速な検索・追加・削除ができるデータ構造。「BST の基本概念」から「バランス木」までを理解していく。
[1.二分探索木（BST）とは？](#1-二分探索木bstとは)
[2.二分探索木の基本操作](#2-二分探索木の基本操作)
[3.平衡二分探索木（Balanced BST）](#3-平衡二分探索木balanced-bst)
[4.典型問題を解いてみる](#4-典型問題を解いてみる)

# 1. 二分探索木（BST）とは？
**BST の基本ルール**
    1. 左部分木のすべての値は、親ノードより小さい
    2. 右部分木のすべての値は、親ノードより大きい
    3. 各ノードの部分木もまた BST である（再帰的構造）

### (1) 二分探索木の例
```markdown
        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. 空いているノードの位置に新しいノードを追加

**<実装>**
```python
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) で可能。

```python
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 つのノードの削除 → 中序順で次の要素（右部分木の最小値）に置き換える

**<実装>**
```python
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）を使ってバランスを保つ
<br>

- **赤黒木（Red-Black Tree）**
    挿入・削除時に色を使ってバランスを保つ
    Python の set や dict に内部的に使われる

# 4. 典型問題を解いてみる

### 例題1. BST の挿入
**問題: N 個の整数を BST に挿入し、順番に出力せよ。**
> [参考： ABC315 B - Insert BST](https://atcoder.jp/contests/abc315/tasks/abc315_b)
<details><summary> 回答　</summary>

```python
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)  # ルートを出力
```
</details>

### 例題2. BST の探索
**問題: BST に X が含まれているか判定せよ。**
> [参考： ABC318 B - Search BST](https://atcoder.jp/contests/abc318/tasks/abc318_b)
<details><summary> 回答　</summary>

```python
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")
```
</details>