基本情報技術者試験の令和7年度の公開問題を解こう。
今回のテーマは、「2分探索木」である。
正解：イ
2分探索木（Binary Search Tree：BST）とは？
データを効率よく探したり、追加したり、削除したりできるように配置した木構造である。
2分探索木の基本ルール
① 左の子は親より小さい
- 親ノードの左側には、親の値より小さいデータが入る。
親が 10 の場合
→ 左の子には 1・5・8 など、10 より小さい数字。
② 右の子は親より大きい
- 親ノードの右側には、親の値より大きいデータが入る。
親が 10 の場合
→ 右の子には 12・20・35 など、10 より大きい数字。
例でイメージしよう。
例えば、以下の順番で数字を挿入する。
10, 5, 15, 3, 8, 12, 18
このように、2分探索木では、すべてのノードで
左 < 親 < 右
が守られている。
この基本ルールを問題に適用すると、一番小さい値は、dで、一番大きな値は、gである。
選択肢をみると、この条件を満たしているのは「イ」とわかる。
コメント