基本情報技術者試験 - 令和8年6月修了 - 問5

値が重複しない15個の自然数のデータを一つずつ追加して2分探索木を構成するとき，その構成に関する記述のうち，適切なものはどれか。ここで，途中で木の再構成は行わないものとする。

ア	完全2分木となるデータの追加順が，ただ一つだけ存在する。
イ	完全2分木となるデータの配置が，ただ一つだけ存在する。
ウ	データの追加順にかかわらず，完全2分木となる。
エ	データの追加順にかかわらず，完全2分木とはならない。

◀ 問4　|　▲ 令和8年6月修了問題一覧　|　問6 ▶

答え：イ
分野：テクノロジ系 › 基礎理論 › アルゴリズムとプログラミング › データ構造
解説：
「2分探索木」は，データを追加する順番によって木の形が変わります。したがって「完全2分木になるデータの追加順」は一つとは限らず，複数存在し得ます。しかし，値の大小関係が決まっている以上，「完全2分木という形」（どのノードにどの値が来るか）自体は一意に定まります。これが「イ」の正解理由です。

「ア」は，実際には複数の追加順で完全2分木を構成できます。「ウ」は，追加順によっては偏った木（片方に伸びた木など）になることがあります。「エ」は，適切な順番で追加すれば完全2分木になり得ます。「配置は一意」だが「追加順は一意ではない」という区別が重要です。