平成31年度 春期 午前 問5

✓ これが正解イ根=4 ／ 4─(2, 8) ／ 2─(1, 3) ／ 8─(6, 9) ／ 6─(5, 7)

解説

左が小さく右が大きいという形を、すべての節で保っています。

2分探索木は、どの節から見ても左が小さく右が大きい木です。この決まりは根だけでなく、すべての節で成り立つ必要があります。さらに、直接の子だけでなく、その先の枝ぜんぶに及びます。確かめ方は単純で、節を一つずつ見て左右の大小を調べます。正解の肢では、根が四で、左の枝に一と二と三が並びます。右の枝には五から九までが並び、どれも四より大きい値です。節の二を見ると、左が一で右が三なので決まりを守っています。節の八を見ると、左の枝は五と六と七で、どれも八より小さい値です。節の六も、左が五で右が七なので守っています。どの節でも破れがないので、これが求める木です。なお、この木を左から順にたどると値が小さい順に並びます。並べ直しの手間なく順序が得られるのが、この形の利点です。探すときは根から降りるだけで済みます。

ほかの選択肢はなぜ違うのか

• ア根=1 ／ 1─(2, 3) ／ 2─(…：根が一で、その左の子が二になっています。左は根より小さいという決まりに、最初から反します。根だけを見れば除ける肢です。値を順に詰めただけの形になっています。下まで見る必要がありません。一段目で決着します。並びに規則がありません。
• ウ根=7 ／ 7─(6, 8) ／ 6─(…：節の六の右の子が五になっています。右は親より大きいという決まりに反します。根の周りは守れているので、下まで見る必要があります。枝の奥に破れが隠れている例です。根から順に降りて確かめます。一か所でも破れれば失格です。
• エ根=9 ／ 9─(7, 8) ／ 7─(…：根が九で、その右の子が八になっています。右は根より大きいという決まりに反します。右の枝ぜんぶが九より小さい値で埋まっています。大小の向きを取り違えた形です。右の枝の値がすべて小さくなっています。向きを入れ替えた形です。