アルゴリズムとプログラミングアルゴリズムとデータ構造

二分探索木（BST）からノード30を削除する。ノード30は左の子ノードに20、右の子ノードに40を持つ。中順後継者（in-order successor）を使った削除後の状態として正しいものはどれか。

ア.ノード20が30の位置に移動し、40は20の右の子になる

イ.ノード30が削除され、20と40は親ノードに直接接続される

ウ.ノード20が削除され、40が30の位置に来て左の子は空になる

エ.ノード40が30の位置に移動し、40のあった場所は空になる正解

解説

BSTの削除は「王位継承」のようなもの。2人の子を持つノードが消えるとき、右部分木で最も小さい者（中順後継者）が跡を継ぐ。

なぜエが正解か

中順後継者は「右部分木の最も左のノード」。ノード30の右部分木の根は40。40に左の子がないため、40自身が中順後継者になる。30を40の値で上書きし、元の40のノードを削除する。結果: 40が30のあった位置に移動し、40のあった場所は空になる。

なぜアは間違いか

20が30の位置に移動するのは中順前継者（in-order predecessor）を使った場合の一例だが、20の右に40が来る形は構造的に誤り。

なぜイは間違いか

20と40が親ノードに直接接続される方式は誤り。BSTの構造を保てない場合がある。

なぜウは間違いか

20が削除されるのは完全に誤り。削除対象はノード30。

出典: AI生成問題（学習用）

← 前の問題

n個の要素をマージソートで整列するとき、マージ操作の回数として正しいものはどれか。8要素の場合は何回か。

次の問題 →

サイズ7のハッシュテーブル（インデックス0〜6）に線形探査法でキー15, 22, 8, 29を順番に挿入する。ハッシュ関数 h(k) = k mod 7 を使用する。挿入後のテーブルの状態として正しいものはどれか。