二分木の走査

木の走査は、決めた順序で各ノードを一度ずつ処理する。先行順、通りがけ順、帰りがけ順は、左部分木を下って戻り、右部分木へ進むという同じ再帰経路を使う。違いは visit(node) を二つの再帰呼び出しの前、間、後のどこに置くかだけ。この一行を動かすと出力順が変わるが、下降と復帰の経路は変わらない。

時間は O(n)、再帰の補助空間は木の高さ h に対して O(h)。根—左—右、左—根—右、左—右—根を別々のアルゴリズムとして覚える必要はない。同じ経路で記録する時点を変えている。

同じ経路で記録位置を動かす

visit(node) は表示、収集、加算などの処理を表す。再帰の骨格は次のとおり。

def traverse(node):
    if node is None:
        return
    # visit(node)  <- 先行順はここ
    traverse(node.left)
    # visit(node)  <- 通りがけ順はここ
    traverse(node.right)
    # visit(node)  <- 帰りがけ順はここ

二つの traverse(...) は常に左、右の順に呼ばれ、空の子 None で基底条件に達して戻る。先行順は到着直後、通りがけ順は左部分木の終了後、帰りがけ順は両部分木の終了後に記録する。

子を呼ぶたびに、親の上に新しいフレームが積まれる。親は一時停止して子を待ち、スタック上に残る。通りがけ順や帰りがけ順で親が子の後に記録されるのは、子の処理が先に終わり、その後で親が visit へ進むためだ。

ラベルには A、B、C などの文字を使う。走査は任意の二分木で動き、二分探索木である必要はない。通りがけ順で整列されるのは BST の性質であり、走査そのものの保証ではない。

二分木を走査するステップ

既定では、木の基礎と同じ、枝の深さが異なる七ノードの木を先行順でたどる。

        A
      /   \
     B     C
    / \   /
   D   E F
      /
     G

関係は A → B, C、B → D, E、C → F、E → G。各ノードで記録し、左、右へ再帰する。

1. A を呼ぶ。スタックは一フレーム。A を記録して出力は A、左へ進む。
2. B を呼び、二フレームになる。B を記録して A B、左へ進む。
3. D を呼び、三フレームになる。D を記録して A B D。両方の子は None なので即座に戻り、D も B へ戻る。
4. B の左が終了したので右の E を呼び、再び三フレームになる。E を記録して A B D E、左へ進む。
5. G を呼ぶと非空ノードのフレームは四つとなり、表示上の最大に達する。G を記録して A B D E G。空の子から戻り、G、E、B の順に終了して A へ戻る。
6. A の左部分木が終わり、右の C を呼ぶ。二フレームで C を記録し、A B D E G C。左へ進む。
7. F を呼び、三フレームになる。F を記録して A B D E G C F。F、C、A の順に終了し、スタックが空になる。

先行順は A B D E G C F で、根 A が最初。パネルの最大は A, B, E, G の四フレームで、高さ 3 に一を足した数となる。空の子への基底呼び出しは即座に戻り、パネルの非空ノードのフレームには数えない。

同じ経路の別の時点で記録する

通りがけ順は二つの呼び出しの間で記録し、D B G E A F C となる。左部分木が終わってから自分を記録し、右部分木へ進む。A は左部分木と右部分木の出力の間にあり、列の中央である必要はない。

帰りがけ順は両方の呼び出しの後で記録し、D G E B F C A となる。親は全て子の後に現れ、根 A は最後になる。

七つの非空ノードを呼び出して戻る順番は共通で、文字を記録する時点だけが変わる。先行順は木を上から複製、直列化するときに使える。通りがけ順は BST のキーを整列順に出す。帰りがけ順は木の解放や式木の評価など、子の結果がそろってから親を処理する用途に向く。

スタックの深さを確認する理由

各ノードの処理回数は定数なので時間計算量は O(n)。空間は終了していない呼び出しの数、つまり現在の経路の長さで決まる。平衡木の高さはおよそ log₂ n。一つの子だけが続く鎖では、非空ノードのフレームが n 個になる。偏った木のプリセットでは七フレーム全てが積まれる。

補助空間 O(h) は、平衡木では O(log n)、鎖では O(n) となる。十分に深い鎖はスタックオーバーフローを起こす。信頼できない入力には明示的なスタックを使える。Morris 走査は一時的なポインターのつながりを使い、補助スタックを減らす方法だ。木の高さを抑えることは、平衡木の利点でもある。収集結果の配列まで含めるなら、別に O(n) の出力領域が必要になる。

境界ケース

• 空の木：traverse(None) がすぐ戻り、どの順序でも出力は空。
• 一ノード：根だけを出力し、三つの順序が一致する。非空ノードのフレームは一つ。
• 子が一つ：欠けた側でも traverse(None) を呼んで即座に戻る。既定の C と E は左の子だけだが、記録のタイミングは保たれる。
• 葉：両方の空の子から即座に戻り、再帰が折り返す。
• 鎖に退化した木：全ての順序で正しいが、深さは n。大きな入力では反復走査を使う。

よくある間違い

• 三つの順序を別々のアルゴリズムとして扱い、visit の位置だけが違うことを見落とす。
• 根が常に最初だと思う。先行順では前、通りがけ順では両部分木の間、帰りがけ順では最後。空の部分木があると、通りがけ順での具体的な位置も変わる。
• if node is None: return を忘れ、空の子のフィールドを参照して失敗する。空の子は記録せず戻る。
• 通りがけ順なら整列されると思う。BST の順序不変条件が必要であり、任意の木では D B G E A F C のような走査順にすぎない。
• 深い木のスタック量を無視する。明示的なスタックや他の反復走査で、実行環境の再帰上限を避けられる。