基本情報 平成28年度 春期 問5｜テクノロジ系に関する問題

答えは a「a=6, b=7」 です。

2分探索木のルール：左の子＜親＜右の子（子孫すべて）。1〜10の数字を木に配るとき、この大小関係を守るパズル。

中順巡回（左→根→右の順）で数値が昇順1,2,3...,10になる性質を使うと、各ノードの位置から自動的に値が決まります。

👉 覚え方：2分探索木の中順巡回＝昇順整列。

図の構造から、a,bの位置を中順で何番目かカウント→6番目、7番目とわかれば正解。

なぜこれが正解か

正解は a（a=6、b=7）。

2分探索木（BST: Binary Search Tree）の不変条件：任意ノードについて、左部分木の全ての値＜ノード値＜右部分木の全ての値。

中順巡回（in-order traversal: 左→根→右）で全ノードを訪問すると、値が昇順（1, 2, 3, ..., 10）に並ぶ性質が成立。問題の図にある10ノードに対し中順巡回順序を辿り、a・bの位置が何番目かを数えると、aは6番目で値6、bは7番目で値7と確定。

各選択肢の解説

• a a=6, b=7：正解。中順巡回順での位置と一致。
• b a=6, b=8：bの位置誤り。
• c a=7, b=8：両方の位置誤り。
• d a=7, b=9：両方誤り。

覚え方・ひっかけ注意

「BSTの中順巡回＝昇順整列」が最強の解法ツール。木の構造図から：

1. 中順巡回の順序で全ノードに番号を振る（1から）

2. その番号がそのままノードの値

試験ではBSTの性質（左<親<右）を直接適用するのではなく、中順巡回テクニックで素早く解くのが定石。木構造を描き直して位置確認する練習が有効。

理論的背景

2分探索木（BST）はO(log n)の検索性能を持つ基本データ構造。理想的にバランスされた木では検索・挿入・削除がO(log n)だが、最悪ケース（連鎖型に縮退）ではO(n)に劣化。これを回避するため自己平衡2分探索木が発展：AVL木（Adelson-Velsky-Landis、平衡因子で回転）、赤黒木（C++ STL map、Linux カーネル）、B木／B+木（DBインデックス、ファイルシステム）、Splay木（自己調整）、Treap（優先度ヒープ＋BST）。

実務での使われ方

• DBインデックス：B+木が主流（MySQL InnoDB等）
• C++ std::map／std::set：赤黒木
• Linuxプロセススケジューラ（CFS）：赤黒木でランキュー管理
• ファイルシステム：ext4・NTFS・ZFSのメタデータ管理
• コンパイラのシンボルテーブル

試験での位置づけ

データ構造・アルゴリズム分野の頻出テーマ。基本情報ではBSTの基本操作・巡回、応用情報・データベーススペシャリストではB木・B+木・インデックス構造・ハッシュ法との比較、自己平衡木の挿入・削除アルゴリズムまで踏み込む。

選択肢の発展補足

3種類の巡回：

• 前順（pre-order）：根→左→右　（式木の前置記法）
• 中順（in-order）：左→根→右　（BSTで昇順）
• 後順（post-order）：左→右→根　（式木の後置記法、ディレクトリ削除）
• 幅優先（level-order）：レベルごと（キュー使用）

BSTとハッシュテーブルの比較：

• ハッシュ：平均O(1)、最悪O(n)、順序保持不可、範囲検索不可
• BST：O(log n)、順序保持、範囲検索可能、最小/最大が容易

NoSQLのインデックス戦略では用途に応じて使い分け（B+木：レンジクエリ、LSM木：書き込み重視・Cassandra/LevelDB、ハッシュ：等価検索）。永続データ構造（Persistent Data Structure）、ロックフリーデータ構造等の発展テーマも応用情報以上では論点。試験対策はBSTの基本性質（中順＝昇順）の活用と自己平衡木・B+木の役割理解で上位資格までカバー可能。