問題プレビューID: e656d47e基本情報技術者試験 午前免除試験 2015年6月28日

問 5
基本情報技術者試験 午前免除試験 2015年6月28日

次の 2 分探索木に 12 を追加したとき,追加された節 12 の位置を正しく表している図はどれか。

解説

正解は「ウ」です。

2 分探索木では,すべての節について「左の子およびその子孫の値 < 節の値 < 右の子およびその子孫の値」が成り立ちます。12 を追加するときは,根から順に大小を比較して進むべき方向を決めます。

  1. 12 > 8 なので,根 8 の右部分木へ進む。
  2. 12 > 10 なので,節 10 の右部分木へ進む。
  3. 12 < 15 なので,節 15 の左部分木へ進む。
  4. 節 15 の左の子は 13 であり,12 < 13 なので,13 の左の子として 12 を追加する。

したがって,12 は 13 の左の子になります。これを表しているのは「ウ」です。

  • ア: 15 の左に 12,右に 13 を置いており,12 < 13 の関係に反します。
  • イ: 12 を 10 の左の子に置いており,12 > 10 の関係に反します。
  • エ: 15 の左に 13,右に 12 を置いており,12 < 15 であるのに 15 の右部分木に入る点が誤りです。

関連問題

本文が同じ・似ている問題を表示しています