木構造と2分探索木：ノード探索と先行順・中間順・後行順走査のトレース術

階層的なデータ表現やデータベースのインデックス（B-Tree等）の基礎となる最重要データ構造が「木構造（ツリー構造：Tree Structure）」です。

特に「2分探索木（Binary Search Tree）」は、大小関係に基づいたノードの配置ルールと、先行順・中間順・後行順という3大深さ優先走査のトレース問題がアルゴリズム分野で頻出します。

本記事では、木構造の基礎用語から2分探索木の不変条件、走査順序の見分け方、ノード追加・削除のポインタ操作までを図解で分かりやすく徹底解説します。

1. 木構造の基本用語と2分探索木の黄金ルール

木構造は、節（ノード）と枝（エッジ）で親子関係を表現するデータ構造です。

【2分探索木の決定的なルール】

すべてのノードにおいて、「左の子（部分木）のすべての値 ＜ 親の値 ＜ 右の子（部分木）のすべての値」という大小関係が厳密に成立します。このルールにより、根から大小比較を繰り返すだけで二分探索と同様の O(log n) で目的ノードを検索できます。

2. 3大深さ優先走査（先行順・中間順・後行順）の見分け方

木構造のすべてのノードを巡回（走査：Traversal）する際、どのタイミングでノードの値を処理するかによって3つの走査法に分かれます。

3. 【実戦トレース】走査順序を一瞬で見抜くテクニック

木のノードの周りに「反時計回りの輪郭線（アウトライン）」を引くイメージを持つと、暗記に頼らず機械的に走査順序を特定できます。

1. 根（50）の真上からスタートし、木全体の輪郭をなぞるように左下へ進む。

2. 先行順：ノードの「左側」を通過した順に値を記録する（50 → 30 → 20 → 40 → 70 → 60 → 80）。

3. 中間順：ノードの「真下」を通過した順に値を記録する（20 → 30 → 40 → 50 → 60 → 70 → 80 ＝ 昇順！）。

4. 後行順：ノードの「右側」を通過した順に値を記録する（20 → 40 → 30 → 60 → 80 → 70 → 50）。

4. 実戦演習：2分探索木へのノード追加

初期状態が空の2分探索木に対して、データ「30, 15, 45, 10, 20, 40, 50」をこの順序で1つずつ挿入したとき、中間順（In-order）で走査した結果として正しいものはどれか。

【選択肢】

• ア: 30, 15, 10, 20, 45, 40, 50

• イ: 10, 15, 20, 30, 40, 45, 50

• ウ: 10, 20, 15, 40, 50, 45, 30

• エ: 50, 45, 40, 30, 20, 15, 10

【解説と解答】

正解：イ（10, 15, 20, 30, 40, 45, 50）

• 2分探索木の最大の性質は、

• 「どのような順序で挿入しても、中間順（In-order）で走査すれば必ずすべての値が昇順（小さい順）に並ぶ」

• という点です。

• 選択肢の中で完全に昇順に並んでいるのは「イ」だけなので、木を実際に手描きしなくても問題文を見た瞬間に即答できます。

5. まとめ：木構造を即答するチェックシート

1. 「左 ＜ 親 ＜ 右」が2分探索木の不変条件。

2. 中間順（通りがけ順）＝ 昇順ソート順（左 → 親 → 右）。

3. 先行順 ＝ 親 → 左 → 右、後行順 ＝ 左 → 右 → 親。

4. 探索の計算量はバランス時 $O(\log n)$、最悪の一直線時 $O(n)$。