BST 削除 — ノード削除の3つのケース
二分探索木からノードを削除する3つのケースを理解します：リーフノード、子が1つのノード、in-order successor 戦略を使用した子が2つのノード。
Deletion
詳細な説明
BST 削除：3つのケース
BST からのノード削除は挿入よりも複雑です。部分木が接続されているノードを削除しながら BST の性質を維持する必要があるためです。
ケース 1：リーフノードの削除
最も単純なケースです。ノードに子がないため、親のポインタを null に設定するだけで削除できます。
削除前: 4 を削除後:
5 5
/ \ / \
3 7 3 7
/ \ \
1 4 1 （リーフだったので削除）
ケース 2：子が1つのノードの削除
ノードを唯一の子で置換します。子が削除されたノードの位置を引き継ぎます。
削除前: 3 を削除後（子 1 が1つ）:
5 5
/ \ / \
3 7 1 7
/
1
ケース 3：子が2つのノードの削除
複雑なケースです。in-order successor（右部分木の最小ノード）を見つけ、その値を削除するノードにコピーし、in-order successor を再帰的に削除します。
削除前: 5 を削除後（in-order successor は 6）:
5 6
/ \ / \
3 8 3 8
/ \ \
6 9 9
なぜ In-Order Successor なのか？
in-order successor は左部分木のすべての値よりも大きい最小の値です。削除するノードをこの値で置換すると BST の性質が保持されます。代わりに in-order predecessor（左部分木の最大値）を使用することもできます。どちらのアプローチも有効です。
時間計算量
- 平均: O(log n) — ノードと successor の検索は両方とも O(h) 時間
- 最悪: O(n) — 高さがノード数に等しい退化木の場合
ユースケース
BST 削除はコーディング面接で最も頻繁に問われるトピックの1つです。再帰的な木の操作、ポインタ管理、BST 不変条件の理解をテストします。実際の応用にはメモリ内インデックスからのエントリ削除、優先度キューの削除操作の実装、順序付き集合の管理があります。