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

選択肢

• アア：根が1、左の子が2（さらに左の子4・右の子5）、右の子が3（さらに左の子6・右の子7、6の右の子8・9）の木
• イイ：根が4、左の子が2（さらに左の子1・右の子3）、右の子が8（さらに左の子6・右の子9、6の左の子5・右の子7）の木
• ウウ：根が7、左の子が6（さらに左の子4・右の子5）、右の子が8（さらに左の子3・右の子9、3の左の子1・右の子2）の木
• エエ：根が9、左の子が7（さらに左の子1・右の子2）、右の子が8（さらに左の子5・右の子6、5の左の子3・右の子4）の木

正解と解説

正解：イ イ：根が4、左の子が2（さらに左の子1・右の子3）、右の子が8（さらに左の子6・右の子9、6の左の子5・右の子7）の木

2分探索木は、任意のノードについて左部分木の全値がそのノードより小さく、右部分木の全値が大きいという条件を満たす木である。イは根が4で、左部分木が1・2・3のみ、右部分木が5〜9のみとなっている。さらに部分木の内部でも、2の左が1・右が3、8の左が6（その左5・右7）・右が9と、どのノードでも条件が崩れていない。

選択肢ごとの解説

• ア根1の左部分木に2以上の値が並んでおり、左が小さいという条件を満たさない。
• イ根4を境に左が1〜3、右が5〜9に分かれ、各ノードでも大小関係が保たれている。
• ウ根7の右部分木に3や1・2といった7より小さい値が含まれており条件を満たさない。
• エ根9の左部分木に7・8が入るのはよいが、8の部分木の配置が大小順になっていない。

この問題に出た用語

• 2分探索木
• 2分探索

同じ分野の他の問題

• 次のプログラム中の a と b に入れる正しい答えの組合せを、解答群の中から選べ。ここで、配列の要素番号は1から始まる。…2026年度 公開問題 科目B 問4
• 次のプログラム中の a と b に入れる正しい答えの組合せを、解答群の中から選べ。ここで、配列の要素番号は1から始まる。…2025年度 公開問題 科目B 問3
• 図の木構造は2分探索木である。a〜gの値の大小関係として，適切なものはどれか。ここで，a〜gの値は重複しないものとする。2025年度 公開問題 科目A 問3
• 次のプログラム中の に入れる正しい答えを、解答群の中から選べ。ここで、配列の要素番号は1から始まる。 図1に示すグラフの…2024年度 公開問題 科目B 問3
• 双方向のポインタをもつリスト構造のデータを表に示す。この表において新たな社員Gを社員Aと社員Kの間に追加する。追加後の表…2023年度 公開問題 科目A 問2