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

同じ木でも、読み出す順序が変わるのはなぜでしょうか？

親の値を処理するタイミングが違うからです。先行順・中間順・後行順を一つの木で比べ、二分探索木の検索と削除も確認します。

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

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

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

この例では重複キーを使わず、左部分木の全ての値＜親＜右部分木の全ての値とします。探索時間は木の高さhに比例してO(h)。平衡ならO(log n)、片側へ偏ると最悪O(n)です。

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

木構造のすべてのノードを巡回（走査：Traversal）する際、どのタイミングでノードの値を処理するかによって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）。

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

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

【選択肢】

1. 30, 15, 10, 20, 45, 40, 50

2. 10, 15, 20, 30, 40, 45, 50

3. 10, 20, 15, 40, 50, 45, 30

4. 50, 45, 40, 30, 20, 15, 10

解説と解答

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

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

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

• という点です。

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

本文で使う木を確認する

          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80

左部分木を全て処理してから親、右部分木へ進む中間順では、20、30、40、50、60、70、80と出力されます。左の子だけでなく、左部分木全体に大小条件が必要です。

追加・削除では何をつなぎ替えるのか

1. 根から比較し、左・右へ進んで、空いている子の位置へ挿入します。重複キーを許す場合は扱いを別に決めます。

2. 親からその葉への参照を外します。

3. 親を、その子へつなぎ替えます。根なら根の参照を更新します。

4. 右部分木の最小値などで対象の値を置き換え、その値を持っていたノードを削除します。大小条件が保たれるか確認します。

50を削除するなら、右部分木の最小値60を根へ移し、元の60のノードを外せます。先行順の値だけでは任意の木の形を一意に保存できない場合があり、空の子の印なども必要です。

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

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

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

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

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

出典と仕様を確認する

IPA：FEシラバス Ver.9.2

Princeton：二分探索木