二分探索木（BST）をもっと深く理解する（後半）
前半では、BST の基本ルール、探索・挿入の流れ、そして中順走査による「ソート済み順」の取得までを整理しました。 後半では、BST を本当に使いこなすために欠かせない 削除処理、バランスの問題、計算量の深掘り、 そして Java の実務で BST をどう扱うべきか（TreeMap / TreeSet の裏側） を丁寧に解説します。
BST は「シンプルに見えて奥が深い」構造です。 後半ではその奥深さを、初心者でも理解できるようにかみ砕いていきます。
BST の削除はなぜ難しいのか（3つのケースを理解する）
BST の削除は、探索や挿入よりも難しく感じる読者が多いです。 理由は、削除には 3つのケース があり、それぞれ処理が異なるからです。
ケース1：削除するノードが「葉」の場合
子がいないので、そのノードを単純に消すだけです。
ケース2：削除するノードが「子を1つだけ持つ」場合
その子を削除するノードの位置に繋ぎ替えます。
ケース3：削除するノードが「子を2つ持つ」場合
最も複雑なケースです。 右部分木の中で「最小の値」を持つノード（中順走査で次に来る値）を探し、 その値を削除対象ノードにコピーし、 コピー元のノードを削除します。
この「右部分木の最小値を使う」というのが BST 削除の定番パターンです。
Javaで書く BST の削除（基本実装）
削除処理を Java で書くと次のようになります。
public static TreeNode delete(TreeNode root, int value) {
if (root == null) return null;
if (value < root.value) {
root.left = delete(root.left, value);
} else if (value > root.value) {
root.right = delete(root.right, value);
} else {
if (root.left == null) return root.right;
if (root.right == null) return root.left;
TreeNode minNode = findMin(root.right);
root.value = minNode.value;
root.right = delete(root.right, minNode.value);
}
return root;
}
private static TreeNode findMin(TreeNode node) {
while (node.left != null) {
node = node.left;
}
return node;
}
深掘り：なぜ「右部分木の最小値」を使うのか
BST のルールを壊さずに値を置き換えるためです。
右部分木の最小値は「削除対象ノードより大きい値の中で最も小さい値」なので、 その値を削除対象ノードにコピーしても BST のルールが崩れません。
この発想が理解できると、BST の削除は一気に分かりやすくなります。
BST のバランス問題（計算量が O(n) に悪化する理由）
BST の計算量は「バランスしているかどうか」で大きく変わります。
理想的な BST
左右の高さが均等 → 探索・挿入・削除が O(log n)
最悪の BST
片側にだけ伸びた「鎖状の木」 → 計算量が O(n)
例えば、次のように昇順の値だけを挿入すると BST は崩壊します。
insert(root, 1);
insert(root, 2);
insert(root, 3);
insert(root, 4);
insert(root, 5);
この場合、木は次のような形になります。
1 2 3 4 5
これはもはや「木」ではなく「リスト」です。 探索も挿入も削除も O(n) になり、BST のメリットが完全に消えます。
深掘り：なぜバランスが崩れると O(n) になるのか
BST の高速性は「左右どちらか一方だけを見る」ことで探索範囲を半分にできる点にあります。 しかし、鎖状の木では「半分にする」という操作ができません。
探索は毎回「次のノードへ1つ進む」だけになり、 線形探索と同じ増え方になります。
この「半分にできるかどうか」が、 BST の計算量を決める最重要ポイントです。
平衡二分探索木（AVL木・赤黒木）との関係
実務では、素朴な BST をそのまま使うことはほとんどありません。 理由は、先ほどの「バランス問題」があるからです。
そこで登場するのが 平衡二分探索木（Balanced BST） です。
平衡木の代表例
AVL木 赤黒木（Red-Black Tree） Treap Splay Tree
これらは「挿入や削除のたびに自動でバランスを調整する」仕組みを持っています。 そのため、計算量が常に O(log n) に保たれます。
Java の TreeMap / TreeSet の正体
Java の TreeMap と TreeSet は 赤黒木（Red-Black Tree） を内部で使っています。
つまり、Java の標準ライブラリは「自動でバランスを取ってくれる BST」なのです。
BST とセキュリティ（DoS攻撃の観点）
セキュリティスペシャリストの視点では、 BST は「攻撃者が形を操作できるデータ構造」として注意が必要です。
危険な例
ユーザー入力をそのまま BST に挿入する 攻撃者が「昇順のデータ」を大量に送る BST が鎖状になり、計算量が O(n) に悪化 サーバーが極端に遅くなる（DoS攻撃成立）
安全にするための対策
平衡木を使う（TreeMap / TreeSet） 入力データを検証する 大量データを BST に入れない 計算量が悪化する可能性を常に監視する
BST は便利ですが、 「形が入力に依存する」という性質が攻撃者に悪用される可能性があります。
BST の計算量を実務レベルで理解する
BST の計算量は次のように整理できます。
バランスしている場合
探索：O(log n) 挿入：O(log n) 削除：O(log n)
バランスが崩れた場合
探索：O(n) 挿入：O(n) 削除：O(n)
この差は非常に大きく、 データ量が増えるほどパフォーマンスに影響します。
そのため、実務では「自前の BST」よりも 「平衡木ベースの標準ライブラリ」を使うのが基本です。
BST を使いこなすための最終ポイント
BST を深く理解するために、次の3つを意識すると効果的です。
左は小さい・右は大きいというルールを常に意識する
探索・挿入・削除のすべてがこのルールに基づいて動く。
バランスが高速性の鍵
半分に絞り込めるかどうかが計算量を決める。
平衡木を使うのが実務の基本
TreeMap / TreeSet は赤黒木なので、常に O(log n) を保証してくれる。
この3つが理解できれば、 BST は「ただの木構造」ではなく「高速な探索構造」として見えるようになります。
後半のまとめ
後半では、BST を実務レベルで使いこなすための内容を扱いました。
削除処理（3つのケース） バランスが崩れたときの計算量悪化 平衡二分探索木（AVL・赤黒木）との関係 TreeMap / TreeSet の裏側 セキュリティ・パフォーマンスの観点
BST はシンプルな構造ですが、 その奥には「高速化」「バランス」「安全性」という深いテーマがあります。