木構造の基礎概念

定義と特徴

木構造は、再帰的に定義される階層型データ構造です。要素数が n (n ≥ 0) の有限集合であり、n = 0 の場合は空木と呼ばれます。非空木において以下の条件を満たします：

• 根ノードは唯一存在し、前駆ノードを持ちません。
• 根以外の子ノードは、互いに素な部分木として分類され、各ノードは厳密に1つの親を持ちます。
• 各ノードは0個以上の後続ノード（子ノード）を持てます。

主要用語

• 次数（Degree）：あるノードが直接持つ子ノードの数。木全体の最大次数を「木の次数」と呼びます。
• 階層・深さ・高さ：根を1階層とし、下方向に進むごとに階層が増加します。深さは根からの距離、高さは葉からの距離で定義されます。木の高さは最大階層数と一致します。
• パスとパス長：上位ノードから下位ノードへ辿るノード列をパス、通過する辺の数をパス長と呼びます。
• 順序木と非順序木：子ノードの左右順序が意味を持つものを順序木、順序が重要でないものを非順序木と区別します。
• 森（Forest）：互いに接続していない複数の木を集合として扱ったもの。

数理的性質

• ノード総数 ＝ 全ノードの次数の合計 ＋ 1
• 次数 m の木において、i 階層の最大ノード数は m^(i-1)
• 高さ h の m 分木における最大ノード数：(m^h - 1) / (m - 1)
• n 個のノードを持つ m 分木的最小高さ：⌈log_m(n(m-1) + 1)⌉

二分木（Binary Tree）

基本仕様と特殊形式

二分木は、各ノードの子が最大2つ（左・右）に制限された順序木です。再帰定義に基づき、空木または「根＋左部分木＋右部分木」の組合せで構成されます。左右の順序を入れ替えると別の構造とみなされます。

代表的な特殊型：

• 全二分木（Full Binary Tree）：最終階層のみ葉ノードが存在し、1次のノードを持たない。ノード番号 i に対し、親は ⌊i/2⌋、子は 2i, 2i+1。
• 完備二分木（Complete Binary Tree）：最終階層以外は満杯で、葉ノードは左寄せに配置される。配列による効率的なインデックスマッピングが可能。
• 二分探索木（BST）：左部分木の全値 ＜ 根の値 ＜ 右部分木の全値 を満たす探索向け構造。
• 平衡二分木（AVL木）：各ノードにおける左部分木と右部分木の高さ差（平衡因子）が ±1 以内。

二分木の数理的性質

• 葉ノード数 n₀ と 2次ノード数 n₂ の関係：n₀ = n₂ + 1
• i 階層の最大ノード数：2^(i-1)
• 高さ h の最大ノード数：2^h - 1
• 完備二分木の高さ計算：⌈log₂(n+1)⌉ または ⌊log₂n⌋ + 1

記憶構造の実装パターン

配列ベース（順序構造）：

インデックスを階層順にマッピングするため、完備二分木に最適です。しかし、片側のみが伸びた単枝木ではメモリ利用率が著しく低下します。

ポインタベース（連結構造）：

各ノードが左右の子ポインタを保持します。親ノードへの逆引きが必要な場合、三叉構造（親ポインタを追加）を採用することで探索コストを削減できます。

走査アルゴリズムと実装

深さ優先走査（DFS）

再帰呼び出しを用いて、根・左・右の訪問順序で分類されます。

// 先行走査（根 → 左 → 右）
void traverse_preorder(Node* current) {
    if (current == nullptr) return;
    process_node(current);
    traverse_preorder(current->left);
    traverse_preorder(current->right);
}

// 中間走査（左 → 根 → 右）
void traverse_inorder(Node* current) {
    if (current == nullptr) return;
    traverse_inorder(current->left);
    process_node(current);
    traverse_inorder(current->right);
}

// 後行走査（左 → 右 → 根）
void traverse_postorder(Node* current) {
    if (current == nullptr) return;
    traverse_postorder(current->left);
    traverse_postorder(current->right);
    process_node(current);
}

木の高さ計算に応用：

void traverse_levelorder(Node* root) {
    if (root == nullptr) return;
    
    std::queue work_queue;
    work_queue.push(root);
    
    while (!work_queue.empty()) {
        Node* current = work_queue.front();
        work_queue.pop();
        
        process_node(current);
        
        if (current->left != nullptr) work_queue.push(current->left);
        if (current->right != nullptr) work_queue.push(current->right);
    }
}

走査結果からの木構造復元

単一の走査列では構造が一意に定まりません。ただし、中間走査列と先行または後行のいずれかを組み合わせて参照することで、木構造を数学的に一意に復元可能です。

スレッド付き二分木

空ポインタを「前駆ノード」および「後続ノード」への参照に再利用し、再帰なしでの効率的な走査を実現します。

struct ThreadedNode {
    int value;
    ThreadedNode* left;
    ThreadedNode* right;
    bool left_is_thread;  // true: 前駆スレッド
    bool right_is_thread; // true: 後続スレッド
};

// 中間走査ベースの線化処理
void build_inorder_threads(ThreadedNode* current, ThreadedNode*& prev) {
    if (current == nullptr) return;
    
    build_inorder_threads(current->left, prev);
    
    if (current->left == nullptr) {
        current->left = prev;
        current->left_is_thread = true;
    }
    if (prev != nullptr && prev->right == nullptr) {
        prev->right = current;
        prev->right_is_thread = true;
    }
    prev = current;
    
    build_inorder_threads(current->right, prev);
}

先行線化では、左ポインタを上書きする前に右部分木の参照を退避する処理（ループ回避）が必須となります。

一般木・森林の表現手法

• 親配列表現：各要素が親のインデックスを保持。親ノードの検索は高速だが、子ノードの列挙には全探索が必要。
• 子リスト表現：各ノードが子ノードへの連結リストを保持。子の数が可変の場合に柔軟。
• 子・兄弟表現：各ノードが「最初の子」と「次の兄弟」へのポインタを保持。これにより任意の多分木を二分木に変換可能。

森林も同様に、各木の根を最初の木の根、その兄弟を次の木の根とみなすことで二分木に変換できます。

応用：探索木・平衡木・ハフマン木

二分探索木（BST）の操作

// 探索処理
Node* search_bst(Node* root, int target) {
    while (root != nullptr && root->value != target) {
        root = (target < root->value) ? root->left : root->right;
    }
    return root;
}

// 挿入処理
bool insert_bst(Node*& root, int target) {
    if (root == nullptr) {
        root = new Node{target, nullptr, nullptr};
        return true;
    }
    if (root->value == target) return false; // 重複排除
    return (target < root->value) 
           ? insert_bst(root->left, target) 
           : insert_bst(root->right, target);
}

削除処理は3パターンに分類されます：

1. 葉ノード：直接削除。
2. 子が1つのノード：子を親に接続し直して置換。
3. 子が2つのノード：右部分木の最小値（後継ノード）または左部分木の最大値（前駆ノード）で置換後、置換元のノードを1または2のケースとして処理。

平衡二分木（AVL木）

挿入・削除時に平衡因子が ±2 になった時点で、最小不平衡部分木に対して回転処理（左回転・右回転・左右回転など）を適用し、高さを O(log n) に維持します。探索・挿入・削除の計算量は最悪ケースでも対数時間となります。

ハフマン木と符号化

葉ノードに出現頻度（重み）を割り当てた場合、木全体の重み付きパス長（WPL）を最小化する構造をハフマン木と呼びます。

構築手順：

1. 各ノードを独立な木として森を形成。
2. 森から根の重みが最小の2木を選択し、新しい親ノードの子として結合（新重み ＝ 両者の和）。
3. 選択した2木を森から削除し、新木を追加。
4. 森の要素数が1になるまで2〜3を反復。

生成された二分木の根から葉へ向かう経路（左：0, 右：1）を文字の符号とすることで、接頭符号性（どの符号も他の符号のプレフィックスにならない）を保証し、データ圧縮効率が最大化されます。