平成31年度 春期 基本情報技術者試験 午前 問5
テクノロジ／アルゴリズム2分探索木として適切なものはどれか。ここで，数字1〜9は，各ノード（節）の値を表す。
出典：平成31年度 春期 基本情報技術者試験 午前 問5
- ア2分探索木ア
- イ2分探索木イ
- ウ2分探索木ウ
- エ2分探索木エ
正解：イ
解説
2分探索木は，どの節についても「左部分木の値はすべてその節の値より小さく，右部分木の値はすべてその節の値より大きい」という条件を満たす木構造です。四つの図についてこの条件を確認すると，イだけが根からすべての節でこの大小関係を満たしています。
選択肢ごとの解説
- ア誤り。根1の左の子が2になっており，左部分木の値は根より小さくなければならないという条件を満たしていません。
- イ正しい。根4の左部分木（2，1，3）はすべて4より小さく，右部分木（8，6，9，5，7）はすべて4より大きく，各節でも同様の大小関係が成り立っています。
- ウ誤り。根7の右部分木（8を根とする部分木）に1，2，3など7より小さい値が含まれており，右側は根より大きい値だけにするという条件を満たしていません。
- エ誤り。根9の右部分木（8を根とする部分木）に9より小さい値が含まれており，右側は根より大きい値だけにするという条件を満たしていません。