基本情報技術者試験
2004年度 ＝ 平成16年度・秋期
午前
問12
次の２分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで２分探索木を再構成するには、削除された要素の位置にどの要素を移動すればよいか。
ア 9
イ 10
ウ 13
エ 14
解答
ウ
解説
２分探索木
は、どのノードに着目しても、
その左部分木のノードのキーの最大値 ＜ キー値 ＜ その右部分木のノードのキーの最小値
が成立する２分木です。したがって、12の位置には、10より大きく14より小さい節点を移動しなければなりません。これを満たすのは
ウ
です。
