平成28年度 秋期 午前 問6

✓ これが正解イ根 17。17 の左の子が 14，右の子が 19。14 の左の子が 10，右の子が 16。19 の左の子が 18。

解説

どの節でも左が小さく右が大きい木が当たります。

2分探索木は、どの節から見ても、左側にぶら下がる値がその節より小さく、右側にぶら下がる値がその節より大きい、という約束を守っている木です。確かめ方は単純で、親と左の子、親と右の子という組を一つずつ取り出し、大小が約束どおりかを当てていくだけで足ります。一つでも破っている組が見つかれば、その木は当てはまりません。当たった木は、根の左側に集まる値がすべて根より小さく、右側に集まる値がすべて根より大きく、さらに枝分かれした先の親子でも同じ関係が保たれていました。注意したいのは、根のすぐ下だけを見て済ませないことです。破れているのが孫の代であっても条件を満たさなくなるので、親子の組を漏らさず当てていきます。

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

• ア根 16。16 の左の子が 15，右の子…：根16の左に15、その15の左に10、右に14がぶら下がる木です。15の右の子が14で親より小さいので、右側は親より大きいという約束を孫の代で破っています。根のすぐ下だけでは見つかりません。
• ウ根 18。18 の左の子が 16，右の子…：根18の左に16、その16の左に15、右に14がぶら下がる木です。16の右の子が14で親より小さく、しかも左の子の15よりも小さいので、左右の大小関係が二重に崩れています。
• エ根 20。20 の左の子が 18，右の子…：根20の右の子が19で、右側は親より大きいという約束が根のすぐ下で破れています。さらにその19の下に15と16が並びますが、右の子である16も19より小さく、同じ約束を繰り返し破っています。