2分探索木の形から値の大小関係を並べる考え方
基本情報技術者試験 令和7年度 問3 ／ アルゴリズムとプログラミング › データ構造
過去問にチャレンジ
図の木構造は2分探索木である。a～gの値の大小関係として，適切なものはどれか。ここで，a～gの値は重複しないものとする。
- ア
a＜b＜d＜e＜c＜f＜g
- イ
d＜b＜e＜a＜f＜c＜g
- ウ
d＜e＜f＜g＜b＜c＜a
- エ
g＜f＜c＜e＜d＜b＜a
会話形式の解説
講師今回は2分探索木の図を見て、節の値の大小を正しく並べる問題です。注目点は、ある節から見て左側と右側にどんな値が入るかという規則です。
受験者2分探索木は、左の子が親より小さくて、右の子が親より大きい木でしたよね。親子の組を一つずつ比べればよいのでしょうか。
講師方向は合っています。ただ、正確には「左部分木の値はすべてその節より小さく、右部分木の値はすべてその節より大きい」です。部分木とは、ある節から下にぶら下がっている枝全体のことです。直接の子だけでなく、孫以下にもこの規則が当てはまります。
受験者では図に当てはめてみます。根aの左の子がb、右の子がcです。bの下は左がd、右がeなので、d＜b＜eになります。cの下は左がf、右がgなので、f＜c＜gです。
講師そのとおりです。では、根aはこの二つの並びのどこに入りますか。
受験者aの左部分木にはd、b、eが入っているので、aはその3つより大きいです。右部分木のf、c、gよりは小さいです。なので、d＜b＜e＜a＜f＜c＜gになります。
講師正解です。この並びは選択肢の中に一つだけあります。ほかの選択肢がなぜ誤りかも確認しましょう。根aが最小になっている並びはどうですか。
受験者bはaの左の子なので、b＜aでなければなりません。aが最小だとa＜bになってしまうので合いません。dがbより大きくなっているのも、dがbの左の子であることに反します。
講師そうですね。逆にaが最大になっている並びは、どこがおかしいでしょうか。
受験者cはaの右の子なのでaより大きいはずですが、aが最大だとc＜aになっています。aの右側にあるfやgもaより小さくなっています。それと、eがbより小さく置かれているので、b＜eにも反しています。
講師よく見えています。最後の、gが最小でaが最大の並びはどうでしょう。d＜bやb＜aの部分は合っているので、少し迷いやすいかもしれません。
受験者合っている部分があっても、cの右の子のgが最小なのはf＜c＜gに反します。eがbより小さいのも誤りです。それに、左側のdやeが右側のc、f、gより大きくなっているので、部分木の規則にも合いません。
講師そのとおりです。反する箇所が一つでも見つかれば、その選択肢は除外できます。全部を細かく比べなくても大丈夫です。
受験者整理すると、左の部分木全体、その節、右の部分木全体の順に小さい値から並ぶということですね。
講師はい。その「左→節→右」の順にたどる方法を中間順といい、2分探索木を中間順でたどると値は昇順に並びます。一方、節→左→右の先行順や、左→右→節の後行順でたどった並びは昇順になりません。順序の名前を取り違えないよう注意してください。また、よくある間違いは、eがbより大きいことだけを見て、aとの関係を見落とすことです。eはaの左部分木にあるので、aよりは小さくなります。
まとめ
2分探索木では、ある節の左部分木の値はすべてその節より小さく、右部分木の値はすべてその節より大きくなります。この規則は直接の親子だけでなく、部分木全体に対して成り立ちます。図の木では、d＜b＜e、f＜c＜gに根aを加えて、d＜b＜e＜a＜f＜c＜gと決まります。この並びは、木を中間順（左→節→右）でたどった結果と一致します。選択肢を検討するときは、親子の関係に反する箇所を一つ見つければ、その選択肢を除外できます。
解答・解説
正解はイです
この問題のテーマ
2分探索木の形から、各節の値の大小関係を正しく並べられるかを問う問題です。左部分木と右部分木の値が、節に対してどちら側に来るかを理解しているかが問われます。
解き方の考え方
図では、根aの左の子がb、右の子がcです。bの子は左がd、右がeで、cの子は左がf、右がgです。2分探索木では、ある節の左部分木の値はすべてその節より小さく、右部分木の値はすべてその節より大きくなります。そこで、bの部分木からd＜b＜e、cの部分木からf＜c＜gが得られます。さらにaは左部分木（d, b, e）のどれよりも大きく、右部分木（f, c, g）のどれよりも小さいので、全体はd＜b＜e＜a＜f＜c＜gと決まります。この並びは、左・節・右の順にたどる中間順の結果とも一致します。
選択肢ごとの解説
- ×ア a＜b＜d＜e＜c＜f＜gアのa＜b＜d＜…という並びでは、根aが最小になっています。bはaの左の子なのでb＜aでなければならず、a＜bは条件に反します。また、dはbの左の子なのでd＜bとなるはずですが、アではb＜dになっています。
- ○イ d＜b＜e＜a＜f＜c＜gイのd＜b＜e＜a＜f＜c＜gは、左部分木の値が節より小さく、右部分木の値が節より大きいという条件をすべての節で満たしています。木を中間順でたどったときの昇順の並びとも一致するので、これが正解です。
- ×ウ d＜e＜f＜g＜b＜c＜aウの並びではaが最大になっています。しかし、cはaの右の子なのでa＜cでなければならず、c＜aは誤りです。aの右部分木にあるfやgもaより小さくなっていて、条件に反します。さらに、eはbの右の子なのでb＜eとなるはずですが、ウではe＜bになっています。
- ×エ g＜f＜c＜e＜d＜b＜aエの並びのうち、d＜bやb＜aの部分は木の条件に合っています。しかし、cの右の子gが最小になっていて、f＜c＜gという関係に反します。また、eがbより小さく置かれているのでb＜eにも反します。aの左部分木にあるeやdが、右部分木のc、f、gより大きくなっている点も誤りです。
補足
直接の親子だけを見て、孫の位置にある値と根との関係を見落とすのがよくある間違いです。たとえば、eはbより大きいものの、aの左部分木に属しているのでaよりは小さくなります。先行順（節→左→右）や後行順（左→右→節）でたどった並びは昇順にならないので、中間順と混同しないよう注意しましょう。
POINT
- 2分探索木では、ある節の左部分木の値はすべてその節より小さく、右部分木の値はすべてその節より大きくなります。
- この規則は直接の親子関係だけでなく、部分木全体に対して成り立ちます。
- 2分探索木を中間順（左→節→右）でたどると、値は昇順に並びます。
- 選択肢を検討するときは、親子の関係を一つずつ確かめ、反する箇所を一つ見つければその選択肢を除外できます。