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

解説

正解は3です。 2分探索木では、どの節点でも、左部分木の値はその節点より小さく、右部分木の値は大きくなっています。 図の木では、根6の右の子が8で、8の右の子が太線で囲まれた削除対象の12です。 12の左部分木は10（子は9と11）、右部分木は14（子は13と15）です。 削除した位置には、左部分木の最大値か右部分木の最小値を移せば、大小関係が保たれます。 左部分木の最大値は11、右部分木の最小値は13です。 【選択肢別解説】 1：× 9を12の位置に移すと、左部分木に残る10と11が9より大きくなります。 左側は小さいという条件が崩れるので誤りです。 2：× 10は左部分木の根なので、移すとその位置が空き、子の9と11を並べ直す必要が生じます。 移動するだけでは再構成できないので誤りです。 3：○ 13は右部分木の最小値です。 12の位置に移すと、左側の9〜11はすべて13より小さく、右側の14と15は大きいので条件が保たれます。 13は葉なので、移した後に空きも生じません。 4：× 14を移すと、右部分木に残る13が14より小さいのに右側に来てしまいます。 右側は大きいという条件が崩れるので誤りです。 【ポイント】 子を2つもつ節点を削除するときは、「左部分木の最大値」か「右部分木の最小値」で置き換えます。 本問では左部分木の最大値11が選択肢にないので、13が正解です。