基本情報技術者試験「2分探索木」の問題
2分探索木(BST)が満たすべき構造的性質として最も適切なものはどれか。
ア任意のノードについて、左部分木の全ての値がそのノードより小さく、右部分木の全ての値が大きい
イ任意のノードについて、その値が左右どちらの子の値以上でもあり、結果として根に格納された値が木全体の最大値となる
ウ全ての葉が同じ深さに並び、根から葉までの経路長が全て等しくなっている
エ各ノードが最大3個の子を持ち、子の個数に応じてキーを内部に保持する
正解
ア．任意のノードについて、左部分木の全ての値がそのノードより小さく、右部分木の全ての値が大きい
2分探索木は各ノードを基準に左部分木の全値が小さく、右部分木の全値が大きいという順序条件を満たす。これにより根から比較しながら片側へ進む二分探索が可能になり、正しい。
?選択肢ごとの解説
ア ○2分探索木は各ノードを基準に左部分木の全値が小さく、右部分木の全値が大きいという順序条件を満たす。これにより根から比較しながら片側へ進む二分探索が可能になり、正しい。
イ ×ノードの値が左右の子以上で根が最大値になるのはヒープ(最大ヒープ)の性質であり、左右の大小関係を定める2分探索木とは異なる。
ウ ×全ての葉が同じ深さで経路長が等しいのは完全2分木や平衡木が近づける形であり、順序関係を定める2分探索木の定義そのものではない。
エ ×各ノードが複数の子と複数キーを持つのは多分木やB木の特徴であり、子が最大2個の2分探索木とは構造が異なる。
✎くわしく
2分探索木は左<親<右の順序条件で値を配置し、中順走査で昇順列が得られる。探索・挿入・削除は木の高さに比例し平均O(log n)だが、偏ると最悪O(n)になる。ヒープの大小条件やB木の多分岐と区別することが核心である。
✓本番での押さえどころ
試験のコツ
『左<親<右』が2分探索木、『親≧子(または親≦子)』がヒープと一文で区別する。中順走査=昇順も合わせて覚える。
覚え方
2分探索木は『左は小さい、右は大きい』と数直線の左右で覚える。根を中心に小と大が振り分けられる。
よくある誤り
2分探索木の左右の大小条件をヒープの親子条件と取り違える誤りが多い。順序か優先度かで区別する。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0125