修了試験 2017-12-10実施分 基本情報技術者試験 問5

解説

正解は3です。 2分探索木では、各節の左の部分木の値はその節より小さく、右の部分木の値はその節より大きくなります。 図の木では、12の左の子は10（その子は9と11）、右の子は14（その子は13と15）です。 子を2つもつ節を削除するときは、左部分木の最大値か右部分木の最小値を移せば大小関係が保たれます。 【選択肢別解説】 1：× 9は左部分木の最小値です。 9を12の位置に移すと、左側の10や11が9より大きくなり、2分探索木の条件が崩れます。 2：× 10を移すと、10の子だった9と11の行き場が別に必要になります。 移動するだけでは木を再構成できません。 3：○ 13は右部分木の最小値で、子をもたない葉です。 12の位置に移すと、左側の9、10、11はすべて13より小さく、右側の14、15は13より大きいので条件が保たれます。 4：× 14を移すと、14の子だった13と15を付け替える必要があります。 移動するだけでは再構成できません。 【ポイント】 削除する節の代わりに使えるのは、中間順（小さい順）で直前の値か直後の値です。 この木では直前が11、直後が13で、選択肢にある13が正解になります。