問題プレビューID: 0c03edf1基本情報技術者試験 2019年(平成31年度)春期 午前

問 5
基本情報技術者試験 2019年(平成31年度)春期 午前

2 分探索木として適切なものはどれか。ここで,数字 1 〜 9 は,各ノード(節)の値を表す。

解説

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 が配置されており、条件(親 < 右)を満たしません。

したがって、正解は イ です。

関連問題

本文が同じ・似ている問題を表示しています