二分探索木（BST）とは何か、またその操作の計算量複雑度は何か？

Question

Accepted Answer

**二分探索木**とは、順序付けの不変条件を持つ二分木です：すべてのノードについて、**左の部分木のすべてのキーはより小さく**、**右の部分木のすべてのキーはより大きい**。これにより、各ステップで問題を半分にして検索できます。

## なぜ重要なのか

```text
        8
       / \
      3    10
     / \     \
    1   6     14     left < node < right at every node
```

## 検索と挿入

```python
def search(node, key):
    while node:
        if key == node.val: return node
        node = node.left if key < node.val else node.right  # go one way
    return None

def insert(node, key):
    if node is None: return Node(key)
    if key < node.val: node.left  = insert(node.left, key)
    else:              node.right = insert(node.right, key)
    return node
```

## 計算量

| 操作 | バランス済み | 最悪（退化） |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |

**最悪ケース**はキーがソート順に挿入される場合に発生します。木は高さ `n` のリンクリストに退化します。

## トレードオフ

- **強み：** O(n) での順序付けられた走査；範囲クエリと後続要素/先行要素をサポート。
- **弱み：** 単体ではバランスの保証がない — O(log n) を保つには AVL または赤黒木の変種が必要。

## なぜ重要なのか

BST は対数時間の操作を持つソート済みの動的データを提供します。これはデータベースインデックスと順序付けられたマップの概念的な祖先です。

退化の問題は**自己バランス木**を動機付けます。これはインタビューで重要なフォローアップトピックです。