令和6年度 秋期 応用情報技術者試験 午前 問5
テクノロジアルゴリズム
この問題は2024(R6)秋 応用情報技術者 午前に出題されたものです。出題時点の法令・制度に基づく内容のため、現行の内容と一致しない場合があります。
本ページの問題文・選択肢は、原本の体裁を Web 表示用に正規化しています（改行・記号・数式・図表参照の調整）。設問の趣旨および正解に影響する変更は加えていません。
次の2分探索木から要素12を削除したとき，その位置に別の要素を移動するだけで2分探索木を再構成するには，削除された要素の位置にどの要素を移動すればよいか。
図の説明テキスト
2分探索木の図。
- ルートノードは6。
- 6の左の子は4、右の子は8。
- 4の左の子は2、右の子は5。
- 2の左の子は1、右の子は3。
- 5は子を持たない。
- 8の左の子は7、右の子は12。
- 7は子を持たない。
- 12の左の子は10、右の子は14。
- 10の左の子は9、右の子は11。
- 14の左の子は13、右の子は15。
各ノードは丸で囲まれ、親子関係が線で結ばれている。
解答・解説を読む
正解: 選択肢ウ
2分探索木から子が2つある節（ノード）を削除して再構成する場合、削除する節の代わりに以下のいずれかの要素を移動させる必要があります。
- 左部分木の最大値（削除する値より小さく、かつ最も大きい値）
- 右部分木の最小値（削除する値より大きく、かつ最も小さい値）
本問において、要素「12」を削除した位置に移動させて2分探索木の性質（左の子 ＜ 親 ＜ 右の子）を維持するためには、「12」の直前または直後の値を選ぶ必要があります。選択肢の中で「12」の直後の値（右部分木の最小値）に該当するのは「13」です。
各選択肢の解説
- ア (9): 「12」より小さい値ですが、最大の要素（直前の値）であるとは限らないため、不適切です。
- イ (10): 「12」より小さい値ですが、最大の要素（直前の値）であるとは限らないため、不適切です。
- ウ (13): 正解です。「12」の右部分木の最小値（直後の値）であり、移動させることで2分探索木の性質を保つことができます。
- エ (14): 「12」より大きい値ですが、「13」が存在するため最小の要素ではありません。これを移動させると木の性質が崩れてしまいます。