平成23年度 特別 基本情報技術者試験 午前 問5

解説

2分探索木は，新しいデータを根から比較し，小さければ左，大きければ右へたどって空いている位置に追加していきます。8→12→5→3→10→7→6の順に挿入すると，根は8，8の左部分木に5，5の左に3，5の右に7，7の左に6，8の右部分木に10，10の右に12という形になります。これに一致するのはエです。

選択肢ごとの解説

• ア誤り。10の左右の子が7と12になっていますが，正しくは8の右部分木側で10の右に12が入り，7は5の右の子（さらにその左に6）となるべきです。
• イ誤り。7の位置が5の右の子止まりで6が7の左の子になっていますが，8の右側の並びが10の右に12ではなく直下に7・12を配置しており，挿入順序と矛盾します。
• ウ誤り。7が5の左部分木の直下（3の右）に単独で入っていますが，実際は7は6と対で5の右側に入るべき位置が異なります。
• エ正しい。8を根とし，5と10がその子，5の子が3と7，7の子が6，10の子が12という配置は，挿入順序どおりにたどった結果と一致します。