BST から値を削除する
BST から値を削除する
このレッスンで分かること
- 削除は
O(h)です- 挿入・検索・min/max と比べて、BST の
削除は段違いに複雑です- 削除アルゴリズムは、削除対象のノードの 子の数 によって 3 つのケースに分かれます
BST から値を削除する とは
BST から指定の値を削除し、削除後の in-order 走査結果を配列で返す関数を実装する。本レッスンでは、BST から値を削除する の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。
挿入・検索・min/max と比べて、BST の 削除 は段違いに複雑です。理由はシンプルで、ノードを取り除いた 穴埋め を上手にやらないと、BST の不変条件が崩れてしまうからです。本レッスンでは bstDelete(arr, target) を実装し、削除後の in-order 走査結果を返します。
削除アルゴリズムは、削除対象のノードの 子の数 によって 3 つのケースに分かれます。1 つずつ丁寧に見ていきましょう。
削除は BST 操作の中で唯一、面接で時間切れになりやすい問題。3 ケースの分岐をスラスラ書けるかが勝負。
ケース 1: 葉ノード (子なし)
もっとも簡単。削除対象に子がないなら、親から見て ただ取り外す だけです。
図のポイント (テキスト併記)
3を削除すれば、5の左の子をnullにして完了です
3 を削除すれば、5 の左の子を null にして完了です。
ケース 2: 子が 1 つだけ
削除対象に子が 1 つだけある場合、その子を削除対象の 位置にそのまま昇格 させます。BST の順序関係はそのまま保たれます。
例えば下の木で 15 を削除する場合、右の子 20 をそのまま 15 の位置に持ち上げれば OK。
ケース 3: 子が 2 つ
ここからが本番です。削除対象に左右両方の子があるとき、そのまま外す ことができません。代わりに、in-order での後継 または in-order での先行 で値を置き換えてから、元の場所を削除します。
in-order 後継とは、右部分木の中で最小のノード のことです。これを successor と呼びます。手順は次の通り。
- 右部分木の最小ノード (左端) を見つける =
successor - 削除対象のノードの値を
successor.valに書き換える - 右部分木に対して
successor.valを 削除 する (これは ケース 1 か 2 に帰着)
このトリックで、BST の不変条件を保ったままノードを取り除けます。
in-order 後継は「ぴったり次に大きい値」なので、置き換えても順序関係が崩れない。先行 (左部分木の最大) でも同じ理屈で OK。
Python での実装例
Python
def deleteNode(node, val):
if node is None:
return None
if val < node.val:
node.left = deleteNode(node.left, val)
elif val > node.val:
node.right = deleteNode(node.right, val)
else:
# 削除対象が見つかった
if node.left is None:
return node.right
if node.right is None:
return node.left
# 子が 2 つ: 右部分木の最小を見つける
succ = node.right
while succ.left is not None:
succ = succ.left
node.val = succ.val
node.right = deleteNode(node.right, succ.val)
return nodeコメントを取り除けば 15 行ほどの短さですが、3 ケースの分岐を完璧にカバーしています。再帰の node.left = deleteNode(...) というパターンは、挿入のときと同じく 親側で子の参照を更新する 鉄則です。
JavaScript での実装例
JavaScript
function deleteNode(node, val) {
if (node === null) return null;
if (val < node.val) {
node.left = deleteNode(node.left, val);
} else if (val > node.val) {
node.right = deleteNode(node.right, val);
} else {
if (node.left === null) return node.right;
if (node.right === null) return node.left;
let succ = node.right;
while (succ.left !== null) succ = succ.left;
node.val = succ.val;
node.right = deleteNode(node.right, succ.val);
}
return node;
}Python と完全に同じロジックを JS に書き換えただけ。BST 操作は言語にほぼ依存せず、再帰 と null チェック だけで書けます。
よくある間違い
第 1 に、削除対象が存在しない (target が木にない) 場合の扱いを忘れること。本問では「何もせず in-order をそのまま返す」とします。再帰版なら自然と「null まで到達して何もしない」挙動になります。第 2 に、子 2 つのケースで succ.val で置き換えた後、その succ を 削除し忘れる こと。これをやらないと木に同じ値が 2 つ存在し、BST が壊れます。第 3 に、ルートを削除するケースを忘れること。再帰の戻り値で root を更新する形にすれば自然と対応できます。
計算量
削除は O(h) です。子 2 つの場合に successor 探しで h 段降り、その後の再削除でさらに h 段降りますが、合計しても O(h)。平衡 BST なら O(log n)、最悪 O(n)。
削除を繰り返すと BST が偏る可能性があるため、本番では
自己平衡木(AVLや赤黒木) の出番。
やってみよう
[10, 5, 15, 3, 7, 13, 20]から15(子 2 つ) を削除し、in-order が[3, 5, 7, 10, 13, 20]になるか確認する- 葉
3の削除、ルート10の削除、子 1 つのノードの削除 (例[10, 5, 15, 3, 7, 20]のように15の左の子を省いた木で15を削除) を一通り試す - 存在しない値
999を削除しても in-order が変わらないことを確認する
よくある質問
Q. BST はなぜ高速ですか？
A. 平衡している場合、検索・挿入・削除がいずれも O(log n) です。各ノードで「左<自分<右」を満たすため、半分ずつ探索範囲が絞れます。ただし偏ると O(n) に劣化するため、実用では赤黒木・AVL 木のような自動平衡化された実装を使います。
Q. in-order 走査で何が得られますか？
A. BST を in-order で巡回するとソート済みの順序で要素が得られます。これが BST と他のツリーの大きな違いで、ソート済みデータの逐次処理に向いています。範囲検索（lo 以上 hi 以下）も簡潔に書けます。
Q. BST に重複値を入れるとどうなりますか？
A. 実装次第ですが、通常は「等しい場合は右に入れる」「カウントを持って同じノードに記録する」のいずれかです。重複が多いユースケースなら TreeMap<Key, Integer> のように出現数を値に持たせる方が探索効率が上がります。
次のレッスン
次は 第 3 章 まとめクイズ で、BST から指定の値を削除し、削除後の in-order 走査結果を配列で返す関数を実装する を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- BST delete の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. BST delete とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 削除対象が葉 / 子 1 つ / 子 2 つ の 3 ケースを正しく扱う
- 子 2 つの場合は in-order 後継 (右部分木の最小) で置き換える
- 存在しない値の削除は何もせず in-order を返す。空木は空配列を返す
入出力例
test-cases.txt
bstDelete([], 5) → []
bstDelete([10], 10) → []
bstDelete([10,5,15], 5) → [10,15]
bstDelete([10,5,15,3,7,13,20], 15) → [3,5,7,10,13,20]
bstDelete([10,5,15,3,7,13,20], 10) → [3,5,7,13,15,20]
bstDelete([10,5,15,null,7], 5) → [7,10,15]
bstDelete([10,5,15], 999) → [5,10,15]