基本情報 2022 サンプル問題 問5：テクノロジ系に関する問題

答えは b です。

2分探索木は 「左の子は親より小さい・右の子は親より大きい」というルールが、全部の場所で守られている木のこと。

選択肢bを見ると(親→左, 右の順):

• 17(親) → 14(左, 17より小) / 19(右, 17より大) ✓
• 14 → 10(左, 14より小) / 16(右, 14より大) ✓
• 19 → 18(左, 19より小) ✓

全部のノードで「左<親<右」が成り立ってる!

ほかの選択肢は、たとえば a だと 15(親) の右に 19 はOKでも、左に「16」みたいな親より大きい数が来ていてルール違反。

👉 覚え方: 「左は小さい、右は大きい」を、根っこから葉っぱまで全部チェック。

2分探索木は 超高速で目的の数字を探せるのが強み(辞書をパッと開くイメージ)。

なぜこれが正解か

正解は b。2分探索木(Binary Search Tree, BST)の定義は 「任意のノードについて、左部分木の全要素 < ノード値 < 右部分木の全要素」。直接の子だけでなく、部分木全体でこの不等式が成立する必要がある。

bの構造: 根17、左部分木{14,10,16}, 右部分木{19,18}

• 17の左部分木は全て17未満(14,10,16 < 17) ✓
• 17の右部分木は全て17より大(19,18 > 17) ✓
• 14の左10、右16もOK / 19の左18もOK

すべて条件を満たす。

各選択肢の解説

• a: 15の子に「10と14と19」が含まれるが、構造を見ると親子関係でBST条件違反のノードがある(例: 15の右部分木に15より小さい値が混在)。
• c: 16の左に15はOKでも、その下に14があり、さらに別ノードで20の左に19等BST条件を破る配置。
• d: 20を根として左に18,10,14,15,16,19 が並ぶが、18の右部分木側に18より大の値があるなど条件違反。

覚え方・ひっかけ注意

「中間順巡回(inorder traversal)で昇順になればBST」 が最強の判定法。bを中間順で読むと 10,14,16,17,18,19 と昇順。他選択肢は中間順が昇順にならない。直接の親子だけ確認して「OK」と早合点しないこと——部分木全体の値域チェックが必須。

データ構造としての本質

2分探索木(BST)は 動的集合(dynamic set) の代表的実装で、検索・挿入・削除を平均 O(log n) で行える。中間順巡回が昇順列を返す性質から「整列済み配列の動的版」と捉えられる。理論的には 比較ベース のデータ構造で、入力順序に依存して木の形状が変化する。

計算量とバランス問題

• 平均: O(log n) — 入力がランダムなら木の高さは ⌈log₂(n+1)⌉ 程度。
• 最悪: O(n) — 昇順/降順に挿入すると線形リスト化し、性能が劇的に劣化。

この欠点を解消するのが 平衡二分探索木:

• AVL木: 左右部分木の高さ差を1以下に保つ(回転操作で再平衡化)。
• 赤黒木: ノードに色を持たせ、特定の不変条件で平衡化。C++ STL の std::map/std::set、Java の TreeMap/TreeSet で採用。
• B木/B+木: 多分木に拡張し、ディスク IO を最小化(DBMS のインデックスで標準)。

削除操作の難所

ノード削除は3パターン:

1. 葉ノード: そのまま削除。

2. 子1つ: 子で置き換え。

3. 子2つ: 中間順後継(右部分木の最小ノード) または中間順前任で置換。これを誤るとBST条件が壊れる。

試験での位置づけ

データ構造の必出単元。基本情報技術者試験では「BSTの判定」「中間順/前順/後順巡回の結果」「ハフマン木」「ヒープ」と並んで頻出。応用情報以降では平衡化、B木、トライ木、スプレー木まで範囲拡大。

選択肢の発展補足

• 判定アルゴリズム: 再帰的に min/max 範囲を引き継いで検証 — `isBST(node, min, max): node.val が (min, max) の範囲内 && 左部分木が (min, node.val) && 右部分木が (node.val, max)`。これが最も効率的(O(n))。
• 重複値の扱い: 厳密な BST では重複を許さないが、`≤` 許容版もある(言語実装による)。本問は厳密版で考えてよい。
• メモリ効率: ノードに左右ポインタ2つ + データを保持するため、配列実装のヒープより空間効率が悪い。キャッシュ局所性も劣るため、現代の実装では B木族(B+木、LSM木)が主流。
• 関連: トライ木(Trie) は文字列検索用の特殊な木で、IPルーティング、辞書検索、オートコンプリートで使用。