二分探索木は部分木の奥までどう確かめる？
基本情報技術者試験 平成31年度春期 午前 問5 ／ アルゴリズムとプログラミング › データ構造
過去問にチャレンジ
2分探索木として適切なものはどれか。ここで，数字1〜9は，各ノード（節）の値を表す。
- ア
- イ
- ウ
- エ
会話形式の解説
講師二分探索木では、各節の左の部分木に小さい値、右の部分木に大きい値があるかを確かめます。
受験者直接つながる子だけを比べればよいのでしょうか。
講師その先も含めて見ます。部分木は、ある節から下につながる節全体です。
受験者では、根が1の図は、左の子が2なので最初から条件に反しますね。
講師そのとおりです。左側の2は根の1より小さくありません。
受験者根が4の図は、左側が1、2、3で、右側が5から9です。これだけで決められますか。
講師さらに節2、8、6も調べます。どの節でも左側が小さく右側が大きいので、この図が適切です。
受験者根が7の図では、右の子の8だけを見るとよさそうですが、その下に3があります。
講師3は根の7より小さいので、右の部分木には置けません。節6の右の子である5も、6より小さく条件に反します。
受験者根が9の図も、右の子の8が9より小さいので不適切ですね。
講師はい。直接の子で違反が見つかる場合も、部分木の奥で見つかる場合もあります。
受験者根だけで判断せず、下の節まで同じ大小関係を確認します。
まとめ
二分探索木では、各節の左の部分木に小さい値、右の部分木に大きい値が必要です。根が4の図は、根の左右にある値だけでなく、節2、8、6でも条件を満たすため適切です。根が1の図と根が9の図は、直接つながる子の値が条件に反します。根が7の図は、右の部分木にある3と、節6の右の子である5が条件に反します。
解答・解説
正解はイです
この問題のテーマ
二分探索木で、各節とその左右の部分木の値の大小関係を判定する問題です。
解き方の考え方
根から順に、左部分木の値はその節より小さく、右部分木の値は大きいかを調べます。直接つながる子だけでなく、その先にある節も条件を満たす必要があります。
選択肢ごとの解説
- ×ア根は1ですが、左の子が2です。左にある値は根より小さくなければならないため、条件に反します。
- ○イ根4の左側には1、2、3、右側には5、6、7、8、9があり、根との大小関係が合っています。節2、8、6についても、それぞれ左側の値が小さく、右側の値が大きいので、二分探索木です。
- ×ウ根7の右部分木に3があります。3は7より小さいため、右部分木に置くことはできません。また、節6の右の子である5も、6より小さく条件に反します。
- ×エ根9の右の子が8です。右側には根より大きい値が必要ですが、8は9より小さいため、条件に反します。
POINT
- 部分木とは、その節から下につながる節全体を指します。
- 根で条件を満たしていても、下位の節でも同じ確認が必要です。
- 直接の子だけを見ると、ウのように部分木の奥にある違反を見落とします。