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

解説

正解は3です。 2分探索木では、各節の左部分木にはその節より小さい値、右部分木には大きい値が入ります。 子を二つもつ節を削除するときは、左部分木の最大値か右部分木の最小値を移動します。 図の12は左の子10、右の子14をもちます。 10の下には9と11、14の下には13と15があります。 12の左部分木の最大値は11、右部分木の最小値は13です。 このうち選択肢にあるのは13です。 【選択肢別解説】 1：× 9を移動すると、左部分木に残る10と11が9より大きくなり、大小関係が崩れます。 2：× 10を移動すると、左部分木に残る11が10より大きくなり、大小関係が崩れます。 3：○ 13は右部分木の最小値なので、移動しても左側は全て13未満、右側は全て13より大きいままです。 4：× 14を移動すると、右部分木に残る13が14より小さくなり、大小関係が崩れます。 【ポイント】 削除した節の位置には、中間順で直前の値か直後の値を入れます。 本問では11も条件を満たしますが、選択肢にはありません。