2分探索木｜科目A-1（応用情報技術者） 令和6年 秋期午前試験 問5
出典：令和6年秋期 午前 問5
分野：アルゴリズムとプログラミング ／ データ構造
次の2分探索木から要素12を削除したとき，その位置に別の要素を移動するだけで2分探索木を再構成するには，削除された要素の位置にどの要素を移動すればよいか。
- ア：9
- イ：10
- ウ：13
- エ：14
TSUNAGARU-ADVICE
まず押さえたいこと
2分探索木で、左右に子をもつ要素を削除するときは、左部分木の最大要素または右部分木の最小要素を削除位置へ移すと、大小関係を保ったまま再構成できます。
迷ったときの判断軸
削除する要素を基準にして、左側から選ぶなら「最も大きい値」、右側から選ぶなら「最も小さい値」を探します。今回のように選択肢から判断する場合は、右部分木のいちばん左にある要素に注目すると見つけやすくなります。
科目Bにつなげるために
特にプロフェッショナルデジタルスキル（システム）試験合格を目指す方は、2分探索木の削除を子なし、子が1つ、子が2つの3パターンに分けて整理しましょう。探索木の更新処理やデータ構造の操作手順を追う問題につながります。
2分探索木では、ある節点の左部分木にはその節点より小さい値、右部分木にはその節点より大きい値を配置します。
要素12には左部分木と右部分木の両方があるため、削除後も2分探索木の大小関係を保つには、左部分木の最大値又は右部分木の最小値を12の位置へ移動します。
この木で12の右部分木にある最小値は13です。13は葉なので、13を12の位置へ移動するだけで、左側の9、10、11は全て13より小さく、右側の14、15は全て13より大きくなり、2分探索木を再構成できます。
したがって、ウが適切です。
❌他選択肢が誤りの理由ア：9
⇒9を12の位置へ移動すると、左部分木に9より大きい10や11が存在することになり、2分探索木の条件を満たしません。
イ：10
⇒10を12の位置へ移動すると、左部分木に10より大きい11が存在することになり、大小関係が崩れます。
エ：14
⇒14を12の位置へ移動すると、右部分木に14より小さい13が存在することになり、2分探索木の条件を満たしません。