平成23年度 特別 午前 問5
データ構造
2分探索木に関する問題
空の2分探索木に，8，12，5，3，10，7，6 の順にデータを与えたときにできる2分探索木はどれか。
〔選択肢の4つの木（○＝節点・線＝枝／親→子の関係を読み取って列挙した）〕 ア 8 の左＝5，右＝10 ／ 5 の左＝3，右＝6 ／ 10 の左＝7，右＝12 イ 8 の左＝5，右＝10 ／ 5 の左＝3，右＝7 ／ 7 の左＝6 ／ 10 の右＝12 ウ 8 の左＝5，右＝12 ／ 5 の左＝3，右＝6 ／ 3 の右＝7 ／ 12 の左＝10 エ 8 の左＝5，右＝12 ／ 5 の左＝3，右＝7 ／ 7 の左＝6 ／ 12 の左＝10
- ア（上記アの木）
- イ（上記イの木）
- ウ（上記ウの木）
- エ（上記エの木）
答えと解説を見る
✓ これが正解エ（上記エの木）
解説
先に与えた値ほど根に近く、後の値がその下に付きます。
2分探索木では、新しい値を入れるとき必ず根から比べ始めます。いま見ている節点より小さければ左へ、大きければ右へ降り、降りた先が空いていればそこに置きます。すでに置かれた節点は動かしません。ですから先に与えられた値ほど上に残り、後から来た値は必ずその下にぶら下がります。最初の8が根になり、次の12が右の子、その次の5が左の子と決まった時点で、根の両側の子はもう変わりません。残る3、10、7、6は、それぞれの側をさらに降りて空いた場所に収まります。判定の軸は、与えられた順序が上下の関係にそのまま表れているか、そして左右の振り分けが値の大小と食い違っていないかの二点です。
ほかの選択肢はなぜ違うのか
- ア（上記アの木）：根の右の子が10になっていますが、10より先に12が与えられているので、右側でいちばん上に来るのは12でなければなりません。左側でも、先に来た7を飛ばして6が5の子に置かれています。
- イ（上記イの木）：左側の形は正しく作れていますが、右側で10が12より上に来ています。与えた順序では12のほうが早いため、この二つの上下が入れ替わっています。
- ウ（上記ウの木）：右側の形は正しく作れていますが、左側で7が3の下に置かれています。7は5より大きい値なので5の右へ降りるはずであり、5より小さい値の下に現れることはありません。
出典：平成23年度 特別 基本情報技術者試験 午前 問5
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）