令和元年度 I-2-2

解説

この問題で問われていること

二分探索木の形が登録順で決まることを使い、図と同じ木になる登録順を選ぶ問題。

解き方

① 各頂点は、その親(祖先)より後に登録されていればよい。図: 8の左に5、右に12、5の左に3・右に7、7の左に6、12の左に10
② 条件は「5と12は8の後」「3と7は5の後」「6は7の後」「10は12の後」。②は10が12より先、③は6が7より先、④は10が12より先、⑤は6が7より先で×
③ ①

正解が正しい理由

二分探索木では、ある頂点は祖先がすべて登録された後に登録されれば、図と同じ位置に入る。図の木では、10は12の子、6は7の子なので、12は10より先、7は6より先に登録されている必要がある。①8,5,7,12,3,10,6はこの条件を満たし、図と同じ木になる。したがって①が正しい。

各選択肢について

• ① 親が子より先に登録されており、図と同じ木になる。これが正答。
• ② 10が12より先に登録されるため、10が8の右の子になり、図と異なる。
• ③ 6が7より先に登録されるため、6が5の右の子になり、図と異なる。
• ④ 10が12より先に登録されるため、図と異なる。
• ⑤ 6が7より先に登録されるため、図と異なる。

覚えるべきポイント

二分探索木の形は、各頂点が祖先より後に登録されるという条件だけで決まる。兄弟どうしの登録順は形に影響しない。