応用情報技術者 2024年 秋期 午前2 問05

二分探索木の削除【午前2解説】

正解の理由

解法ステップ

1. 削除対象ノード（12）を確認する。左右両方に子を持つことを確認する。
2. 左右どちらの中間要素を使うか決める：
   • 通常は右部分木の最小（in-order successor）か左部分木の最大（in-order predecessor）を用いる。
3. 右部分木の最小を求める：12の右部分木（根14）の最左ノードを辿ると13に到達する。13は葉（子を持たない）。
4. 13を12の位置へ移す（または12の値を13に置き換え、元の13ノードを削除する）だけで順序関係が保たれる。
5. 必要なら元の13位置をnullにする（13は葉なので親の子ポインタをnullにすればよい）。

選択肢別の誤答解説

• ア: 9
  9は12の左部分木（12→10→9）に含まれる左側の端の要素ですが、9を12の位置へ移すとBSTの順序が崩れます。12の右部分木にある13や14などは9より大きいため、9をその位置に置くことはできません。
• イ: 10
  10は12の左部分木の根に相当し、左右に子（9と11）を持ちます。10を12の位置へ移すには10の子や元の位置のつなぎ替えが必要で、単に「その位置に移動するだけ」では再構成できません。
• ウ: 13
  13は12の右部分木の最小（in-order successor）であり、かつ葉であるため、移動だけでBSTを保てます（正答）。
• エ: 14
  14は12の右部分木の根であり左右に子（13,15）を持つため、14をそのまま12の位置に移すと元の子のつなぎ替えが必要になります。従って単純移動では不適切です。

よくある誤解

• 「9は12の左部分木にも含まれない」と誤認することがありますが、実際には9は12の左部分木（12→10→9）の左端に位置します。ただし左部分木の最大（前駆）は11であり、9は前駆（最大）でも後続（最小）でもありません。
• 「葉ならどの葉でも置ける」と考える誤り。移動先に置く要素は、その位置において全ての左部分木の要素より大きく、右部分木の要素より小さくなければならず、単に葉であることだけでは不十分です。
• 「必ず前駆を使うべき」との誤解。前駆（左部分木の最大）でも後続（右部分木の最小）でもどちらでもよいが、実際に使える候補（子を余分に持たないもの）が選ばれる。

補足コラム

• 二分探索木のノード削除の標準処理は次の3通りのケースに分かれます：
  1. 子が無い（葉）→ そのノードを単に削除。
  2. 子が1つ → 親がその子を直接指すように置き換える。
  3. 子が2つ → in-order successor（右部分木の最小）または in-order predecessor（左部分木の最大）を用いて置換し、元の位置のノードを削除（その多くは子が最大でも最小でも1個以下であるため処理が簡単）。
• 問題文の条件「その位置に別の要素を移動するだけで」は、置換対象が葉または子を1つしか持たない場合に成立するという観点で読むと操作意図が明確になります。

FAQ