うごく基本情報

平成25年度 春期 問5

アルゴリズムとプログラミング › 木構造・ヒープ ○ 優先

出典:平成25年度 春期 基本情報技術者試験 午前 問5 の問題

出典:平成25年度 春期 基本情報技術者試験 午前 問5

正解と解説を見る

正解:ウ

覚えること:2分探索木で子が2つある節点を消すときは、左の部分木の最大値か、右の部分木の最小値をその位置に移す。

12 の位置には、12 より小さい側(左の部分木)の最大値 11 か、大きい側(右の部分木)の最小値 13 を移せば、2分探索木の性質が保たれます。選択肢にあるのは 13 です(ウ)。10 や 14 を移すと、その子の位置も組み替える必要があります。アの 9 は左の部分木の最大値ではない(最大は 11)ので、移すと 10 や 11 が 9 より大きいのに左側に残り、2分探索木の性質が崩れます。イの 10 とエの 14 は、移すとその子(9 と 11、13 と 15)の位置も組み替える必要があります。

解説はこのサイトが作成したものです。