BST 挿入 — 二分探索木の挿入の仕組み

BST 挿入の仕組み

二分探索木（BST）への挿入は単純な再帰的ルールに従います：新しい値を現在のノードと比較し、小さければ左へ、大きければ右へ進み、null 位置に到達したら新しいリーフノードを作成します。

アルゴリズム

INSERT(root, value):
  if root is NULL:
    return new Node(value)
  if value < root.value:
    root.left = INSERT(root.left, value)
  else if value > root.value:
    root.right = INSERT(root.right, value)
  return root   // 重複は無視

ステップバイステップの例

空の BST にシーケンス [8, 3, 10, 1, 6, 14, 4, 7] を挿入する場合：

1. 8 がルートになる
2. 3 < 8 — 8 の左に配置
3. 10 > 8 — 8 の右に配置
4. 1 < 8, 1 < 3 — 3 の左に配置
5. 6 < 8, 6 > 3 — 3 の右に配置
6. 14 > 8, 14 > 10 — 10 の右に配置
7. 4 < 8, 4 > 3, 4 < 6 — 6 の左に配置
8. 7 < 8, 7 > 3, 7 > 6 — 6 の右に配置

時間計算量

• 平均ケース: O(log n) — 木がある程度バランスしている場合
• 最悪ケース: O(n) — ソート済みデータを挿入すると連結リスト形状の木になる
• 挿入順序が木の形状を直接決定する

重要な性質

すべての挿入後に BST 不変条件が成立する必要があります：任意のノードについて、左部分木のすべての値は厳密に小さく、右部分木のすべての値は厳密に大きい。重複値は通常無視されるか、各ノードのカウントフィールドで処理されます。

挿入順序の重要性

[1, 2, 3, 4, 5] を挿入すると右に偏った退化木（高さ 5）になります。[3, 1, 5, 2, 4] を挿入するとバランスのとれた木（高さ 3）になります。同じ値の集合でも挿入順序によって非常に異なる木の形状になり、検索性能に直接影響します。