基本情報技術者試験 基本情報技術者試験 平成31年度 春期 午前 午前 問5: 2分探索木として適切なものはどれか。ここで，数字 1〜9 は，各ノード（節）の値を表す。

問題本文

2分探索木として適切なものはどれか。ここで，数字 1〜9 は，各ノード（節）の値を表す。

選択肢

• ア.図ア: 根=1。右部分木に 2,3,...,9 を配置するが、内部で左部分木<親<右部分木の条件に違反するノードがある二分木。
• イ.図イ: 根=4、左部分木 = {2 を根とし 1,3 を子}、右部分木 = {8 を根とし 6,9 を子、6 の子に 5,7}。全ノードで左<親<右が成立する正しい二分探索木。
• ウ.図ウ: 根=7。左右配置に二分探索木の順序条件を満たさないノードを含む二分木。
• エ.図エ: 根=9。右部分木に根より小さい値があり、左<親<右の条件に違反する二分木。

正解

イ. 図イ: 根=4、左部分木 = {2 を根とし 1,3 を子}、右部分木 = {8 を根とし 6,9 を子、6 の子に 5,7}。全ノードで左<親<右が成立する正しい二分探索木。

解説

2分探索木の条件は「左部分木の全ノード < 親 < 右部分木の全ノード」。イ (根=4、左部分木 [2:{1,3}]、右部分木 [8:{6:{5,7}, 9}]) は全ノードでこの条件を満たす。イが正解。

選択肢ごとの解説

• ア.根=1 の右に 2,3 を配置 (1<2,1<3 OK) だが、その下に 4-9 を配置する構造で条件が成立しない箇所がある。
• イ.根=4、左=2(<4)、右=8(4)、各部分木でも順序が保たれる。2分探索木の条件を満たし正解。
• ウ.根=7、左=6(<7)、右=8(7) は OK だが、左部分木の下に 4,5,3 配置で順序矛盾がある。
• エ.根=9、左=7(<9)、右=8(9 でない) — 右部分木の値が根より小さく矛盾。