基本情報 令和7年度 科目A 問3：テクノロジ系に関する問題

答えは b（d ＜ b ＜ e ＜ a ＜ f ＜ c ＜ g） です。

「2分探索木」は、データを並べた特別な木の形で、ルール：左の子は親より小さい・右の子は親より大きいになっています。たとえば部活の背の順を、真ん中の人を中心に「自分より小さい子は左、大きい子は右」と振り分けていくイメージ。

図ではa が根っこで、b が左の子、c が右の子。さらに b の下に d（左）と e（右）、c の下に f（左）と g（右）がぶら下がっています。

👉 覚え方：左小さい・右大きい。木を左から下→右の順にたどると（中順走査）必ず小さい順に並ぶので、答えはその並び順そのもの！

ほかの選択肢は左右の大小関係が崩れていて、ルール違反です。

なぜこれが正解か

正解は b。2分探索木の定義は「任意のノードについて、左部分木の全ノード値 ＜ 自ノード値 ＜ 右部分木の全ノード値」。図の構造（根 a、左子 b、右子 c、b の子が d,e、c の子が f,g）に当てはめると：

• a の左部分木（b,d,e）は全て a より小さい → d,b,e ＜ a
• a の右部分木（c,f,g）は全て a より大きい → a ＜ f,c,g
• b の左子 d ＜ b ＜ 右子 e
• c の左子 f ＜ c ＜ 右子 g

以上を統合すると d ＜ b ＜ e ＜ a ＜ f ＜ c ＜ g。

各選択肢の解説

• a：a が最小になっており、根が最小値となるため矛盾。
• b：上記の定義を全て満たす。正解。
• c：a が最大値だが、a の右部分木に c,f,g があるはずで矛盾。
• d：右ほど小さくなる降順構造で、定義と逆。

覚え方・ひっかけ注意

「2分探索木を中順走査（左→根→右）すると必ず昇順になる」 ことを覚えればこの種の問題は瞬殺。中順走査の順序がそのまま答えの不等式になる。試験では図の配置から左右関係を見間違えやすいので、まず根を特定し、左部分木＜根＜右部分木を機械的に書き下す。

理論的背景

2分探索木（Binary Search Tree, BST）は探索・挿入・削除の平均計算量が O(log n) になるデータ構造。ただし最悪計算量は O(n)（偏った木＝退化したリスト構造）になり、これが BST 単独の弱点。中順走査（in-order traversal）の結果が昇順ソートになる性質は、ツリーソート（O(n log n) 平均）の根拠でもある。

実務での使われ方

単純 BST はそのままでは退化リスクがあるため、実務では自己平衡二分探索木が用いられる：AVL 木（左右部分木の高さ差±1以内）、赤黒木（C++ std::map, Java TreeMap, Linux カーネルの CFS スケジューラで採用）、Splay 木、B 木・B+ 木（DBMS のインデックス）等。RDBMS のインデックスは B+ 木が主流で、ディスク I/O 最小化のため多分木構造になっている。

試験での位置づけ

科目A「データ構造とアルゴリズム」の最頻出領域。基本情報では BST の探索手順・走査順（先行／中間／後行）・計算量、削除アルゴリズム（葉・1子・2子のケース分け、後継ノード置換）まで深掘り。基本情報技術者試験ではハッシュ法との比較、空間計算量、平衡木の回転操作（LL/LR/RL/RR）が頻出。

選択肢の発展補足

• 走査順の覚え方：前順（行きがけ）／中順（通りがけ）／後順（帰りがけ）。BSTの中順は昇順、後順は数式の逆ポーランド記法生成等に使う。
• BST 削除の2子ケース：右部分木の最小値（または左部分木の最大値）で置換するのが定石。
• 派生：トライ木（文字列検索）、セグメント木（区間クエリ）、Fenwick 木／BIT（累積和）は応用情報・競技プログラミング寄り。
• 探索木の選択指針：データ件数固定→ハッシュ、範囲検索が必要→BST/B+木、メモリ局所性重視→B木。