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

解説

正解は3です。 2分探索木に新しい値を追加する手順を問う問題です。 2分探索木では、各節について「左の子孫は節より小さく、右の子孫は節より大きい」という関係が保たれます。 追加するときは根から比較をたどり、空いている位置に葉として付け加えます。 元の木は、根8の左に3（その子が1と5）、右に10（その子が9と15）があり、15の左の子が13です。 【選択肢別解説】 1：× 選択肢1（図のア）は、12を節9の右の子に付けています。 12は10より大きいので、10の右側の部分木に入らなければならず、9の下には付きません。 2：× 選択肢2（図のイ）は、10の左の子を12に置き換え、9をその左の子にしています。 追加の操作では既存の節の位置は変わりません。 また12が10の左側にあること自体が大小関係に反します。 3：○ 選択肢3（図のウ）は、15の左の子13の、さらに左の子に12を付けています。 12は8より大きいので右へ、10より大きいので右へ、15より小さいので左へ、13より小さいので左へ進み、空いている13の左に入ります。 4：× 選択肢4（図のエ）は、12を15の右の子に付けています。 12は15より小さいので、15の左側に入らなければなりません。 【ポイント】 2分探索木への追加は、根から「小さければ左、大きければ右」と比較を繰り返し、たどり着いた空の位置に置くだけです。 既存の節を動かさないことも確認しましょう。