木の基礎

木はノードと親子の辺からなります。根だけが親を持たず、ほかの各ノードは一つの親を持ち、循環はありません。そのため根から各ノードへの経路は一つです。根、親、子、葉、深さ、高さ、部分木はこの関係から定まります。木構造はディレクトリ階層、HTML、データベース索引などに使われます。

図では根を上に置き、枝を下へ伸ばします。子がないノードが葉です。ノードの深さは根からそのノードまで、高さはそのノードから最も遠い葉まで数えます。木全体の高さは根の高さです。

木を作るもの

このレッスンのノードは値、左の子、右の子を持つ二分木で、子は最大二つです。下へたどって始点に戻らず、根以外が二つの親を持つこともありません。

• 根：唯一親がなく、このレッスンの走査の入口。
• 葉：子がないノード。
• 内部ノード：少なくとも一つの子を持つノード。
• 部分木：あるノードと全子孫。子も部分木の根なので再帰処理ができる。

A、B、C などの文字でノードを示します。通常の木には大小順序がなく、左の子が親より小さいとは限りません。二分探索木が追加する順序の不変条件と区別してください。

木をステップで追う

既定の Lopsided は不均等な形です。

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

関係は A → B, C、B → D, E、C → F、E → G。七ノードで、葉は D、F、G、内部ノードは A、B、C、E です。C の子は一つ、B は二つで、どちらも有効です。

1. 根を表示：A は唯一親がない。
2. レベルごとに展開：B、C、次に D、E、F、最後に G。各親子接続が辺で、七ノードに循環はない。
3. 葉を示す：D、F、G は子を持たない。
4. 深さを読む：辺数で A は 0、B と C は 1、D と E と F は 2、G は 3。
5. 高さを読む：最長の根から葉への経路 A → B → E → G は三辺。高さ 3 は最大深さに等しい。
6. 形を比べる：同じ七ノードでも、平衡形は高さ 2、この偏りは 3、一本の鎖は 6。ノード数だけでは高さは決まらない。

深さは根からノードまで、高さはノードから最も遠い葉までです。最深の葉の深さが木全体の高さになります。

七ノードで高さ 2 と 6

Balanced は各レベルが満たされた完全な形で、高さ 2。七ノードの二分木で可能な最小高さです。Degenerate は末尾以外が一つの子だけを持つ鎖で、高さ n − 1 = 6 になります。

一本の経路を進む操作は通常、高さに依存します。全走査はどの形でも全ノードを訪ねますが、探索木の位置検索は退化の影響を受けます。AVL 木や赤黒木は平衡規則で対数の高さを保ちます。通常の木にはその保証がありません。

三つの走査順

同じ再帰で値を訪問する時点を変えると、三種類の順序になります。

def traverse(node):
    if node is None:
        return
    # preorder:  visit here  -> node before its subtrees
    traverse(node.left)
    # inorder:   visit here  -> between left and right
    traverse(node.right)
    # postorder: visit here  -> node after its subtrees

• 先行順、ノード→左→右：A B D E G C F。各部分木の根を内容より前に見る。木のコピーや階層のアウトラインに使える。
• 中間順、左→ノード→右：D B G E A F C。ノードは左右の部分木の間。
• 後行順、左→右→ノード：D G E B F C A。子孫を先に処理し、親を後にする。木の解放や部分木サイズの計算に使う。

どれも各ノードを一度ずつ訪れ、順序だけが違います。ここでは結果を示し、木の走査のレッスンではコールスタックで再帰の過程を追います。

境界ケース

• 一ノード：根でも葉でもあり、深さと木の高さは 0。辺で数える規約では空の高さを −1 と置けるので、再帰式は 1 + (−1) = 0。
• 子が一つ：有効。既定の C は左の子だけ。二分は最大二つで、必ず二つではない。
• 退化した鎖：高さ n − 1。経路アクセスがリストのようになる。
• 葉の深さが違う：D と F は 2、G は 3。同じレベルでなくてよい。

よくある間違い

1. 深さと高さを交換する。 深さは根から、高さは葉へ数えます。深い位置の葉でも高さは 0 です。
2. 普通の木を探索木と読む。 左が小さく右が大きいという規則は BST が追加する条件です。
3. 最下段だけを葉とする。 子がなければ位置に関係なく葉です。
4. 走査順を混同する。 部分木の前、間、後のどこでノードを訪れるかが出力と用途を変えます。
5. 木は常に平衡だと思う。 通常の木は鎖に退化できます。低い高さには AVL や赤黒木などの規則が必要です。