二分探索木

二分探索木は各ノードで、左部分木の全値が小さく、右部分木の全値が大きいという規則を保ちます。一比較で片側を除外し、挿入・検索・削除は高さ h の経路を進むため O(h) です。平衡な形や適切なランダム入力の仮定では平均 O(log n) ですが、通常の BST は毎回半分の除外を保証しません。

数当ての「大きい」「小さい」が次を決める仕組みです。平衡な二分なら約二十回で百万の候補を扱えます。BST は判断をノードと参照に保存し、効果は形に依存します。

二分探索木の仕組み

三操作とも根から比較し、小さければ左、大きければ右、一致すれば発見です。経路が終わった後の処理が違います。

insert(value) は空きに達して新しい葉を付け、上の構造は変更しません。一致したら重複を挿入せず終了します。空なら新ノードを根にします。

search(value) は一致で発見、null で未発見です。順序の不変条件が、飛ばした部分木に対象がないことを保証します。

delete(value) は発見後、子の数で分かれます。

• 子なし：親からの参照を null にする。
• 子一つ：親をその子へ直接つなぐ。部分木を保ったまま対象を飛ばしても、親に対する順序は成立する。
• 子二つ：この実装は中間順の後継を使う。右部分木へ一度進み、左端の最小値を探す。これは左部分木の全値より大きく、右の残りより小さい。その値を対象へコピーし、右部分木の元の後継を削除する。後継に左の子はないため、葉か一子の削除に帰着する。先行ノードでも対称に実装できるが、ここでは後継を使う。

操作をステップで追う

プレイヤーは空から始まります。50, 30, 70, 20, 40, 60, 80 を順に入れます。

1. insert(50)：根がなく、比較なしで根になる。
2. insert(30)：30 < 50 で左へ。insert(70) は右へ付く。
3. insert(20)：50、30 と比べ、二回左へ。40、60、80 も各二比較で、30 の右、70 の左、70 の右へ付く。高さ 2 の平衡な形になる。
4. search(40)：50 で左、30 で右、40 で一致。三比較、深さ 2 で発見。
5. delete(20)：50、30 を経て葉 20 を見つけ、30 の左を空にする。
6. delete(30)：子は 40 だけになっている。50 の左を 40 へ向けて 30 を外し、40 を上げる。
7. delete(50)：最初の比較で根に一致し、子が二つある。右の 70、左の 60 へ。60 に左の子がないため後継と分かる。60 を根へコピーし、右部分木にあった元の葉 60 を外す。

最後は根 60、左 40、右 70、70 の右 80 です。各ノードの順序条件は維持されます。

画面は比較した経路を点灯し、未訪問の部分木を薄く保ちます。挿入前に空き位置を示し、削除は切り離し、迂回、後継探索を区別します。後継と対象を破線で結んでから、コピーと取り外しを行います。

時間・空間計算量

通常の BST は平衡化しません。1, 2, 3, 4, 5 の順なら毎回右に付き、鎖になります。辺数の高さは n − 1、最悪操作は O(n)。AVL、赤黒木、treap は各規則で高さを制御します。例えば Java TreeMap は赤黒木を使います。

最大深さスライダーの 3–5 は画面の制約です。深さを超える挿入は理由を表示し、その深さの完全な木の最大ノード数に達すると挿入ボタンを無効にします。実際の BST の制限ではなく、通常の木はさらに退化して伸びられます。

境界ケース

• 空：検索は即未発見、挿入は根を作り、削除は変更なし。
• 根の削除：二子なら後継、一子なら子を根へ昇格。
• 重複挿入：一致で停止。件数フィールドなど別の規約もあるが、一つの木で統一する。
• ない値の削除：null に達し、木は変わらない。
• 唯一のノードの削除：葉の処理で根を空にする。

よくある間違い

• 二子ノードを接続の保存なしに外す。 部分木を失います。ここでは後継値をコピーして後継を外します。同じ不変条件を保つノード移植の実装も可能です。
• 後継を誤る。 右部分木の左端であり、近くの任意の葉や左部分木のノードではありません。先行を使うなら対称な手順全体を使います。
• 整列済み入力で平衡を期待する。 通常の挿入は鎖を作ります。最悪界が必要なら自己平衡木を使います。順序のランダム化も最悪保証ではありません。
• BST とヒープの混同。 BST は左右の順序で整列走査や範囲検索を支えます。ヒープは親子の優先度を制約し、極値を O(1) で見られますが配列は整列しません。