2 分探索木(Binary Search Tree)は、任意のノードにおいて以下の条件を満たす木構造です。
「左の子ノードの値 < 親ノードの値 < 右の子ノードの値」
選択肢の図を確認します。
- ア: ルートが 1 で左の子が 2 となっており、条件(左 < 親)を満たしません。
- イ:
- ルート 4 に対して、左部分木(2, 1, 3)はすべて 4 未満、右部分木(8, 6, 9, 5, 7)はすべて 4 より大きいです。
- ノード 2 に対して、左 1 < 2 < 右 3 です。
- ノード 8 に対して、左部分木(6, 5, 7)はすべて 8 未満、右 9 は 8 より大きいです。
- ノード 6 に対して、左 5 < 6 < 右 7 です。
全てのノードで条件を満たしています。
- ウ: ノード 8 に対して左の子が 3 となっており、3 < 8 は正しいですが、その下で 1, 2 がぶら下がっており構造が不適切です(一般に2分探索木では部分木全体で条件を満たす必要があります)。また、ルート 7 の右にある 8 の左に 3 があるのは正しいですが、図の配置が不自然です。より明確に、イが標準的な 2 分探索木です。
- エ: ルート 9 の右側に 8 が配置されており、条件(親 < 右)を満たしません。
したがって、正解は イ です。