アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20150628 実施分 問5
次の 2 分探索木に 12 を追加したとき，追加された節 12 の位置を正しく表している図はどれか。
元の 2 分探索木: 根 8。8 の左の子 3（3 の左の子 1，右の子 5），8 の右の子 10。10 の左の子 9，右の子 15。15 の左の子 13。
- ア [図] 8 の左に 3（左に 1，右に 5），右に 10。10 の左に 9，右に 15。9 の右の子が 12，15 の左の子が 13。
- イ [図] 8 の左に 3（左に 1，右に 5），右に 10。10 の左に 12，右に 15。12 の左の子が 9，15 の左の子が 13。
- ウ [図] 8 の左に 3（左に 1，右に 5），右に 10。10 の左に 9，右に 15。15 の左の子が 13，13 の左の子が 12。
- エ [図] 8 の左に 3（左に 1，右に 5），右に 10。10 の左に 9，右に 15。15 の左の子が 13，右の子が 12。
出典：基本情報技術者試験 科目A免除 修了試験 20150628 実施分 問5
答えと解説を見る
正解：ウ
覚える知識
2分探索木へのデータ挿入順による形状
2分探索木では根から大小比較をたどり、空いた子の位置に新しい節を挿入する。
この問題で必要なこと
12は8より大、10より大、15より小、13より小なので13の左の子として挿入される。
ひっかけ
13の右側や9の子など大小関係を誤った位置。
この知識の出題：本試験系 1 回・免除試験 2 回（公開問題での観測値）