正解は「イ」です。
2 分探索木とは,任意の節において,左部分木のすべての節の値がその節の値より小さく,右部分木のすべての節の値がその節の値より大きい 2 分木です。各選択肢の構造を確認します。
- ア: 根 16 の左の子 15 に対し,その右の子が 14 である。右の子は親より大きくなければならないが 14 < 15 なので不適切。
- イ: 根 17 に対し,左部分木 {14,10,16} はすべて 17 より小さく,右部分木 {19,18} はすべて 17 より大きい。節 14 は左の子 10 < 14,右の子 16 > 14。節 19 は左の子 18 < 19。すべての条件を満たし適切。
- ウ: 根 18 の左の子 16 に対し,その右の子が 14 である。右の子は親より大きくなければならないが 14 < 16 なので不適切。
- エ: 根 20 の右の子が 19 である。右の子は親より大きくなければならないが 19 < 20 なので不適切。