1.2.4. 木構造

1. 概要

　木構造（Tree Structure）は、データ構造の一種であり、階層的な関係を表現するための非線形データ構造です。木構造は根（ルート）から始まり、枝（エッジ）によって複数の節（ノード）が接続され、最終的に葉（リーフ）と呼ばれる末端ノードに至ります。

　木構造はコンピュータサイエンスの基礎となる重要なデータ構造であり、ファイルシステム、データベースのインデックス、構文解析、検索アルゴリズムなど、多くの場面で応用されています。木構造を理解することは、効率的なアルゴリズムの設計や実装において不可欠です。

2. 詳細説明

2.1. 木構造の基本用語と概念

　木構造は以下の要素から構成されています：

  • 根（ルート）：木の最上位に位置するノード
  • 枝（エッジ）：ノード間を接続する線
  • 葉（リーフ）：子ノードを持たない末端ノード
  • 内部ノード：葉ではないノード（子を持つノード）
  • 親ノード：あるノードに対して上位に接続されているノード
  • 子ノード：あるノードから枝で接続された下位のノード
  • 兄弟：同じ親を持つノード同士
  • 深さ：根からあるノードまでの経路の長さ
  • 高さ：木の最も深い部分の深さ
graph TD
    R["根（ルート）"] --> |"枝（エッジ）"| B["内部ノード"]
    R --> |"枝（エッジ）"| C["内部ノード"]
    B --> |"枝（エッジ）"| D["内部ノード"]
    B --> |"枝（エッジ）"| E["葉（リーフ）"]
    C --> |"枝（エッジ）"| F["葉（リーフ）"]
    D --> |"枝（エッジ）"| G["葉（リーフ）"]
    D --> |"枝（エッジ）"| H["葉（リーフ）"]
    
    classDef root fill:#f96,stroke:#333,stroke-width:2px;
    classDef internal fill:#bbf,stroke:#333,stroke-width:1px;
    classDef leaf fill:#bfb,stroke:#333,stroke-width:1px;
    class R root;
    class B,C,D internal;
    class E,F,G,H leaf;

    %% 補足説明
    depth1["深さ1"] -.-> B
    depth2["深さ2"] -.-> D
    depth0["深さ0"] -.-> R
    siblings["兄弟"] -.-> F
    siblings -.-> E
    parent["親ノード"] -.-> C
    children["子ノード"] -.-> G
    children -.-> H
    height["木の高さ = 3"] -.-> G

図1: 木構造の基本用語

2.2. 木構造の種類

2.2.1. 2分木（バイナリツリー）

　２分木（にぶんぎ）は、バイナリーツリー（binary tree）とも呼ばれます。
　各ノードが最大2つの子ノード（左の子と右の子）を持つ木構造です。2分木はシンプルな構造ながら、多くの応用があります。

2.2.2. 完全2分木（完全バイナリツリー）

　最下層を除くすべての層が完全に埋まっており、最下層は左から順に埋まっている2分木です。ヒープデータ構造の実装などで使用されます。

graph TD
    subgraph "2分木（バイナリツリー）"
    A1((A)) --> B1((B))
    A1 --> C1((C))
    B1 --> D1((D))
    B1 --> E1((E))
    C1 --> F1((F))
    end

    subgraph "完全2分木（完全バイナリツリー）"
    A2((A)) --> B2((B))
    A2 --> C2((C))
    B2 --> D2((D))
    B2 --> E2((E))
    C2 --> F2((F))
    C2 --> G2((G))
    end

    classDef node fill:#bbf,stroke:#333,stroke-width:1px;
    class A1,B1,C1,D1,E1,F1,A2,B2,C2,D2,E2,F2,G2 node;

図2: 2分木と完全2分木の比較

２分木については以下をご参照ください。

2分木を理解する
1. 木構造について　２分木（binary tree）について理解する前に、まずは木構造について確認していきます。　木構…
tech.itq.co.jp
2025.04.01

2.2.3. バランス木

　すべての葉ノードの深さがほぼ同じになるように調整された木構造です。これにより検索や挿入、削除などの操作が効率的に行えます。代表的なバランス木にはAVL木や赤黒木などがあります。

graph TD
    subgraph "バランス木"
    A1((50)) --> B1((30))
    A1 --> C1((70))
    B1 --> D1((20))
    B1 --> E1((40))
    C1 --> F1((60))
    C1 --> G1((80))
    end

    subgraph "非バランス木"
    A2((10)) --> B2((20))
    B2 --> C2((30))
    C2 --> D2((40))
    D2 --> E2((50))
    end

    classDef balanced fill:#bfb,stroke:#333,stroke-width:1px;
    classDef unbalanced fill:#f96,stroke:#333,stroke-width:1px;
    class A1,B1,C1,D1,E1,F1,G1 balanced;
    class A2,B2,C2,D2,E2 unbalanced;

図3: バランス木と非バランス木の比較

2.2.4. 赤黒木

　赤黒木は自己平衡型の2分探索木で、各ノードは赤または黒で色付けされています。次の性質を保持します：

  1. 各ノードは赤か黒
  2. 根ノードは黒
  3. すべての葉（NILノード）は黒
  4. 赤ノードの子は黒（赤ノードが連続しない）
  5. 根から任意の葉までの黒ノードの数（黒高さ）は同じ

　これらの性質により、最悪の場合でも操作の時間計算量がO(log n)となります。

2.2.5. 順序木（ordered tree）

　各ノードの子ノードに順序が定義されている木構造です。子ノードの順番が意味を持ちます。

2.2.6. 多分木（n分木）

　各ノードが最大n個の子ノードを持つことができる木構造です。B木はこの一種であり、ディスクアクセスを最小化するために設計されたバランス探索木です。

2.2.7. 探索木

　データの検索を効率的に行うための木構造です。代表的なものに2分探索木があります。

2.2.8. 2分探索木（バイナリサーチツリー）

　次の性質を持つ2分木です：

  • 左の子孫のすべての値 < 親ノードの値 < 右の子孫のすべての値

　この性質により、検索が効率的に行えます。

graph TD
    A((50)) --> B((30))
    A --> C((70))
    B --> D((20))
    B --> E((40))
    C --> F((60))
    C --> G((80))
    
    classDef node fill:#bbf,stroke:#333,stroke-width:1px;
    class A,B,C,D,E,F,G node;
    
    %% 性質の説明
    leftProp["左の子孫 < 親"]-.->D
    rightProp["親 < 右の子孫"]-.->G
    search["検索: 比較しながら
左右に進む"]-.->E

図4: 2分探索木の例

2.2.9. B木

　ディスクベースのデータベースやファイルシステムで使用される自己平衡型の探索木です。1つのノードに複数のキーと子ノードへの参照を格納でき、効率的なディスクI/Oを実現します。

graph TD
    Root["[30, 60]"] --> N1["[10, 20]"]
    Root --> N2["[40, 50]"]
    Root --> N3["[70, 80, 90]"]
    
    N1 --> L1["<= 10"]
    N1 --> L2["11-20"]
    N1 --> L3["21-29"]
    
    N2 --> L4["31-40"]
    N2 --> L5["41-50"]
    N2 --> L6["51-59"]
    
    N3 --> L7["61-70"]
    N3 --> L8["71-80"]
    N3 --> L9["81-90"]
    N3 --> L10["\>= 91"]
    
    classDef node fill:#f9f,stroke:#333,stroke-width:1px;
    classDef leaf fill:#bfb,stroke:#333,stroke-width:1px;
    class Root,N1,N2,N3 node;
    class L1,L2,L3,L4,L5,L6,L7,L8,L9,L10 leaf;
    
    note["B木の特徴:
• 1ノードに複数キー
• すべての葉は同じ深さ
• ディスクI/O効率化"]

図5: B木の構造

2.2.10. AVL木

　各ノードの左右の部分木の高さの差が1以下であることを保証するバランス2分探索木です。挿入や削除操作後に自動的にバランスを調整します。

graph TD
    subgraph "左回転前"
    A1((A)) --> B1((B))
    A1 --> C1((C))
    C1 --> D1((D))
    C1 --> E1((E))
    end
    
    subgraph "左回転後"
    C2((C)) --> A2((A))
    C2 --> E2((E))
    A2 --> B2((B))
    A2 --> D2((D))
    end
    
    subgraph "右回転前"
    P1((P)) --> Q1((Q))
    P1 --> R1((R))
    Q1 --> S1((S))
    Q1 --> T1((T))
    end
    
    subgraph "右回転後"
    Q2((Q)) --> S2((S))
    Q2 --> P2((P))
    P2 --> T2((T))
    P2 --> R2((R))
    end
    
    classDef before fill:#bbf,stroke:#333,stroke-width:1px;
    classDef after fill:#bfb,stroke:#333,stroke-width:1px;
    class A1,B1,C1,D1,E1,P1,Q1,R1,S1,T1 before;
    class A2,B2,C2,D2,E2,P2,Q2,R2,S2,T2 after;
    
    note["AVL木のバランス調整:
• 左回転: 右部分木が重い場合
• 右回転: 左部分木が重い場合
• 二重回転: 複合的なバランス崩れの場合"]

図6: AVL木の回転操作

木構造の種類 特徴 長所 短所 主な応用
2分木 各ノードは最大2つの子を持つ シンプルで実装が容易 バランスが保証されない 式の表現、基本的なデータ構造
完全2分木 最下層を除き完全に埋まっている 配列での実装が効率的 動的な挿入・削除が難しい ヒープ、優先度付きキュー
2分探索木 左<親<右の順序関係を持つ 検索・挿入・削除がO(h)時間 偏りがあると性能劣化 辞書、シンボルテーブル
AVL木 自己平衡型2分探索木、高さ差≦1 常に平衡状態を保つ 回転操作のオーバーヘッド データベース、メモリ管理
赤黒木 自己平衡型2分探索木、色による制約 AVL木より挿入・削除が高速 実装が複雑 多くの言語のマップ実装、Linux仮想メモリ
B木 多分木、ノードに複数キー ディスクI/Oの最小化 メモリ使用量が多い データベース、ファイルシステム
多分木 各ノードがn個以下の子を持つ 幅広いデータ構造の表現 メモリ効率が低い場合あり ファイルシステム、XML/HTML DOM
順序木 兄弟間に順序関係がある 順序に意味を持たせられる 一般的な操作が複雑になる 構文解析、XMLツリー

表1: 主な木構造の特徴比較表

2.3. 木の巡回法

　木構造の全ノードを訪問する方法には、大きく分けて深さ優先探索と幅優先探索があります。

2.3.1. 深さ優先探索（DFS: Depth-First Search）

　深さ優先探索では、可能な限り深く進んでから戻るというアプローチを取ります。2分木の場合、以下の3種類の巡回順序があります：

  1. 先行順（前順、プレオーダー）：親 → 左の子 → 右の子
  2. 中間順（中順、インオーダー）：左の子 → 親 → 右の子
  3. 後行順（後順、ポストオーダー）：左の子 → 右の子 → 親
graph TD
    A((A)) --> B((B))
    A --> C((C))
    B --> D((D))
    B --> E((E))
    C --> F((F))
    C --> G((G))
    
    classDef node fill:#bbf,stroke:#333,stroke-width:1px;
    class A,B,C,D,E,F,G node;
    
    A:::node -- "①" --> B:::node
    B:::node -- "②" --> D:::node
    D:::node -- "③" --> B:::node
    B:::node -- "④" --> E:::node
    E:::node -- "⑤" --> B:::node
    B:::node -- "⑥" --> A:::node
    A:::node -- "⑦" --> C:::node
    C:::node -- "⑧" --> F:::node
    F:::node -- "⑨" --> C:::node
    C:::node -- "⑩" --> G:::node
    
    visit["訪問順序: A,B,D,E,C,F,G
(親→左→右)"]

図7: 先行順巡回の図解

graph TD
    A((A)) --> B((B))
    A --> C((C))
    B --> D((D))
    B --> E((E))
    C --> F((F))
    C --> G((G))
    
    classDef node fill:#bbf,stroke:#333,stroke-width:1px;
    class A,B,C,D,E,F,G node;
    
    A:::node -- "①" --> B:::node
    B:::node -- "②" --> D:::node
    D:::node -- "③" --> D:::node
    D:::node -- "④" --> B:::node
    B:::node -- "⑤" --> B:::node
    B:::node -- "⑥" --> E:::node
    E:::node -- "⑦" --> E:::node
    E:::node -- "⑧" --> B:::node
    B:::node -- "⑨" --> A:::node
    A:::node -- "⑩" --> A:::node
    
    visit["訪問順序: D,B,E,A,F,C,G
(左→親→右)"]

図8: 中間順巡回の図解

graph TD
    A((A)) --> B((B))
    A --> C((C))
    B --> D((D))
    B --> E((E))
    C --> F((F))
    C --> G((G))
    
    classDef node fill:#bbf,stroke:#333,stroke-width:1px;
    class A,B,C,D,E,F,G node;
    
    A:::node -- "①" --> B:::node
    B:::node -- "②" --> D:::node
    D:::node -- "③" --> D:::node
    D:::node -- "④" --> B:::node
    B:::node -- "⑤" --> E:::node
    E:::node -- "⑥" --> E:::node
    E:::node -- "⑦" --> B:::node
    B:::node -- "⑧" --> B:::node
    B:::node -- "⑨" --> A:::node
    A:::node -- "⑩" --> C:::node
    
    visit["訪問順序: D,E,B,F,G,C,A
(左→右→親)"]

図9: 後行順巡回の図解

2.3.2. 幅優先探索（BFS: Breadth-First Search）

　幅優先探索では、同じ深さのノードをすべて訪問してから次の深さに進みます。レベル順（階層順）巡回とも呼ばれます。

graph TD
    A((A)) --> B((B))
    A --> C((C))
    B --> D((D))
    B --> E((E))
    C --> F((F))
    C --> G((G))
    
    classDef level0 fill:#f96,stroke:#333,stroke-width:2px;
    classDef level1 fill:#bbf,stroke:#333,stroke-width:1px;
    classDef level2 fill:#bfb,stroke:#333,stroke-width:1px;
    class A level0;
    class B,C level1;
    class D,E,F,G level2;
    
    order1["①"] -.-> A
    order2["②"] -.-> B
    order3["③"] -.-> C
    order4["④"] -.-> D
    order5["⑤"] -.-> E
    order6["⑥"] -.-> F
    order7["⑦"] -.-> G
    
    level0["レベル0"] -.-> A
    level1["レベル1"] -.-> B
    level2["レベル2"] -.-> D
    
    visit["訪問順序: A,B,C,D,E,F,G
(レベル順に訪問)"]
    queue["実装時は
キュー使用"]

図10: 幅優先探索の図解

2.4. 節の追加や削除

　木構造、特に2分探索木やバランス木では、データの追加や削除がよく行われる操作です。

2.4.1. 節の追加

　2分探索木への節の追加は、以下のステップで行います：

  1. 根から始め、追加する値と各ノードの値を比較
  2. 値が小さければ左へ、大きければ右へ移動
  3. 適切な位置（葉ノードの位置）に到達したら、新しいノードを追加

　バランス木（AVL木など）の場合は、追加後にバランスを保つための回転操作が必要になる場合があります。

graph TD
    subgraph "ステップ1: 初期状態"
    A1((50)) --> B1((30))
    A1 --> C1((70))
    B1 --> D1((20))
    B1 --> E1((40))
    C1 --> F1((60))
    end
    
    subgraph "ステップ2: 値25の追加を検討"
    A2((50)) --> B2((30))
    A2 --> C2((70))
    B2 --> D2((20))
    B2 --> E2((40))
    C2 --> F2((60))
    
    D2 -. "比較: 25 > 20" .-> X2[" "]
    end
    
    subgraph "ステップ3: 追加完了"
    A3((50)) --> B3((30))
    A3 --> C3((70))
    B3 --> D3((20))
    B3 --> E3((40))
    C3 --> F3((60))
    D3 --> X[" "]
    D3 --> G3((25))
    end
    
    classDef default fill:#bbf,stroke:#333,stroke-width:1px;
    classDef new fill:#bfb,stroke:#333,stroke-width:2px;
    classDef path fill:#f9f,stroke:#333,stroke-width:1px;
    classDef empty fill:white,stroke:white,stroke-width:0px;
    
    class G3 new;
    class X,X2 empty;
    class A2,B2,D2 path;
    
    process["追加手順:\n1. 根から比較開始
2. 値が小さければ左、大きければ右へ移動
3. 適切な位置に到達したら新ノード追加"]

図11: 節の追加の図解

2.4.2. 節の削除

　2分探索木からの節の削除は、次の場合分けで処理します：

  1. 削除するノードが葉の場合：単純に削除
  2. 削除するノードが1つの子を持つ場合：ノードを削除し、その子を親に接続
  3. 削除するノードが2つの子を持つ場合：ノードの中間順での後継ノード（右部分木の最小値）と値を交換し、後継ノードを削除

　バランス木の場合は、削除後にバランスを保つための回転操作が必要になる場合があります。

graph TD
    subgraph "葉ノードの削除（40を削除）"
    A1((50)) --> B1((30))
    A1 --> C1((70))
    B1 --> D1((20))
    B1 --> E1((40))
    C1 --> F1((60))
    C1 --> G1((80))
    
    A2((50)) --> B2((30))
    A2 --> C2((70))
    B2 --> D2((20))
    B2 --> X2[" "]
    C2 --> F2((60))
    C2 --> G2((80))
    
    E1 -. "削除" .-> X2
    end
    
    subgraph "子が1つのノードの削除（30を削除）"
    P1((50)) --> Q1((30))
    P1 --> R1((70))
    Q1 --> S1((20))
    R1 --> T1((60))
    R1 --> U1((80))
    
    P2((50)) --> S2((20))
    P2 --> R2((70))
    R2 --> T2((60))
    R2 --> U2((80))
    
    Q1 -. "削除し、子を親に接続" .-> S2
    end
    
    subgraph "子が2つのノードの削除（50を削除）"
    J1((50)) --> K1((30))
    J1 --> L1((70))
    K1 --> M1((20))
    K1 --> N1((40))
    L1 --> O1((60))
    L1 --> X1((80))
    
    O1 -. "後継者を特定（中間順での次のノード）" .-> J1
    
    J2((60)) --> K2((30))
    J2 --> L2((70))
    K2 --> M2((20))
    K2 --> N2((40))
    L2 --> X3[" "]
    L2 --> X2((80))
    end
    
    classDef default fill:#bbf,stroke:#333,stroke-width:1px;
    classDef deleted fill:#f96,stroke:#999,stroke-width:1px,stroke-dasharray: 5 5;
    classDef empty fill:white,stroke:white,stroke-width:0px;
    classDef replaced fill:#bfb,stroke:#333,stroke-width:2px;
    
    class E1,Q1,J1 deleted;
    class X2,X3 empty;
    class J2 replaced;
    
    note["削除手順は3パターン:
1. 葉: 単純に削除
2. 子が1つ: 子を親に接続
3. 子が2つ: 中間順後継と交換し、後継を削除"]

図12: 節の削除の図解

2.5. ヒープの再構成

　ヒープは完全2分木を用いて実装される優先度付きキューの一種です。ヒープには最小ヒープと最大ヒープがあります。

　ヒープの主な操作には以下があります：

  1. 挿入：
    • 最後の位置（配列の末尾）に要素を追加
    • ヒープ条件が満たされるまで上方向にバブルアップ（上昇）
  2. 最大値/最小値の削除：
    • 根の値を取り出す
    • 最後の要素を根に移動
    • ヒープ条件が満たされるまで下方向にバブルダウン（下降）
  3. ヒープの再構成（ヒープ化）：
    • 任意の配列からヒープを構築するプロセス
    • ボトムアップアプローチが効率的：最後の非葉ノードから始めて根に向かって各部分木をヒープ条件を満たすように調整
graph TD
    subgraph "最大ヒープ"
    A1((100)) --> B1((80))
    A1 --> C1((90))
    B1 --> D1((70))
    B1 --> E1((50))
    C1 --> F1((40))
    C1 --> G1((30))
    
    I1["配列表現: [100, 80, 90, 70, 50, 40, 30]"]
    J1["性質: 親 ≥ 子"]
    end
    
    subgraph "バブルアップ操作（値75の挿入）"
    A2((100)) --> B2((80))
    A2 --> C2((90))
    B2 --> D2((70))
    B2 --> E2((50))
    C2 --> F2((40))
    C2 --> G2((75))
    
    G2 -. "比較: 75 > 40" .-> C2
    
    A3((100)) --> B3((80))
    A3 --> C3((90))
    B3 --> D3((70))
    B3 --> E3((50))
    C3 --> F3((40))
    C3 --> G3((75))
    end
    
    subgraph "バブルダウン操作（最大値抽出後）"
    A4((30)) --> B4((80))
    A4 --> C4((90))
    B4 --> D4((70))
    B4 --> E4((50))
    C4 --> F4((40))
    
    A4 -. "比較: 30 < 90, 30 < 80" .-> Z4[" "]
    
    A5((90)) --> B5((80))
    A5 --> C5((30))
    B5 --> D5((70))
    B5 --> E5((50))
    C5 --> F5((40))
    end
    
    classDef default fill:#bbf,stroke:#333,stroke-width:1px;
    classDef new fill:#bfb,stroke:#333,stroke-width:2px;
    classDef compare fill:#f9f,stroke:#333,stroke-width:1px;
    classDef empty fill:white,stroke:white,stroke-width:0px;
    
    class G2,G3 new;
    class A4,C5 compare;
    class Z4 empty;
    
    note["ヒープ操作:
1. 挿入: 末尾に追加後、バブルアップ
2. 最大値抽出: 根を返し、末尾を根に移動後、バブルダウン
3. ヒープ構築: 非葉から根へ向かってバブルダウン"]

図13: ヒープの構造と操作

2.5.1. ヒープソート

　ヒープソートはヒープデータ構造を利用したソートアルゴリズムです。手順は以下の通りです：

  1. 配列をヒープに変換（ヒープ化）
  2. 最大ヒープから最大値（根）を取り出し、配列の末尾に配置
  3. ヒープサイズを1減らし、ヒープを再構成
  4. すべての要素がソートされるまで2-3を繰り返す

　ヒープソートの時間計算量はO(n log n)で、安定ではありませんが追加のメモリをほとんど必要としないという特徴があります。

3. 応用例

3.1. ファイルシステム

　コンピュータのファイルシステムは、ディレクトリとファイルの階層構造を表現するために木構造（具体的には多分木）を使用しています。これにより、ファイルやフォルダを効率的に整理・検索できます。

3.2. データベースインデックス

　B木やB+木はデータベース管理システムでインデックスとして広く使用されています。これらの木構造により、大量のデータから特定のレコードを高速に検索できます。

3.3. 構文解析

　プログラミング言語のコンパイラやインタプリタでは、ソースコードの構文を解析する際に構文木（パースツリー）が使用されます。これは順序木の一種です。

3.4. 圧縮アルゴリズム

　ハフマン符号化などのデータ圧縮アルゴリズムでは、文字の出現頻度に基づいて2分木（ハフマン木）を構築し、効率的な符号化を実現しています。

3.5. 人工知能

　決定木は機械学習の分類アルゴリズムとして使用されています。また、ゲームAIでのミニマックスアルゴリズムやアルファベータ剪定も木構造を利用しています。

応用例 使用される木構造 理由・特徴 具体例
ファイルシステム 多分木・B木 階層構造の表現、ディスクI/O最適化 Unix/Linuxファイルシステム、NTFS、ext4
データベースインデックス B木・B+木 ブロックアクセスの最小化、範囲検索の効率化 MySQL(InnoDB)、PostgreSQL、Oracle
構文解析 順序木（構文木） 文法構造の階層的表現 コンパイラ、インタプリタ、JSON/XMLパーサー
データ圧縮 2分木（ハフマン木） 出現頻度に基づく可変長符号化 JPEG、MP3、ZIP、GZIP
ネットワークルーティング トライ木（Trie） IPアドレスの効率的な検索 ルーターのルーティングテーブル
機械学習 決定木 特徴に基づく分類の視覚化と判断 ランダムフォレスト、勾配ブースティング決定木
GUI要素 多分木 階層的なUIコンポーネントの表現 DOM、ウィジェットツリー
ゲームAI ミニマックス木 ゲーム状態と可能手の探索 チェス、将棋、囲碁のAI
メモリ管理 AVL木・赤黒木 動的メモリブロック管理の効率化 メモリアロケータ、ガベージコレクタ
計算幾何学 kd木・四分木 多次元空間の効率的な分割と検索 近傍探索、衝突検出、3Dレンダリング

表2: 木構造の応用例とその特徴

4. 例題

例題1: 2分木の巡回

次の2分木について、先行順、中間順、後行順での巡回結果をそれぞれ示せ。

  • 先行順: A, B, D, E, C, F
  • 中間順: D, B, E, A, C, F
  • 後行順: D, E, B, F, C, A

例題2: 2分探索木の構築

次の数値を順に2分探索木に挿入した場合の最終的な木の形を示せ。 50, 30, 70, 20, 40, 60, 80

例題3: ヒープの再構成

次の配列を最大ヒープに再構成する過程を示せ。 [4, 10, 3, 5, 1]

  1. 配列を完全2分木として表現:
  1. 最後の非葉ノードから根に向かってヒープ条件を適用:
    • インデックス1（値10）は既にヒープ条件を満たしている
    • インデックス0（値4）で比較: 4 < 10, 4 > 3 なので4と10を交換
  1. さらに4を見ると、4 < 5 なので交換:
  1. 最終的な最大ヒープ: [10, 5, 3, 4, 1]

例題4: AVL木のバランス調整

次の操作を行った後のAVL木を示せ。 空のAVL木に10, 20, 30, 40, 50の順に挿入する。

  1. 10を挿入: 10
  2. 20を挿入: 10 -> 20
  3. 30を挿入: バランス崩れるため左回転
  1. 40を挿入: 20 -> 30 -> 40
  2. 50を挿入: バランス崩れるため左回転

5. まとめ

　木構造は、階層的なデータを表現・操作するための基本的かつ強力なデータ構造です。本記事では、根、葉、枝などの基本要素から始まり、2分木、完全2分木、バランス木、順序木、多分木、探索木、2分探索木、B木、AVL木などの様々な種類の木構造について解説しました。

　また、深さ優先探索と幅優先探索という2つの基本的な巡回方法、および先行順、後行順、中間順という2分木特有の巡回順序についても説明しました。

　節の追加や削除、特に2分探索木とバランス木におけるそれらの操作と、ヒープデータ構造の再構成方法についても詳しく解説しました。

　木構造は理論的な概念にとどまらず、ファイルシステム、データベース、構文解析、人工知能など、情報処理のさまざまな分野で実際に応用されています。木構造の理解と適切な実装は、効率的なアルゴリズムの設計において不可欠な知識です。

参考文献

  1. トーマス・H・コルメン他, “アルゴリズムイントロダクション 第3版”, 近代科学社, 2013.（Amazonアソシエイトリンク）
  2. 石畑清, “アルゴリズムとデータ構造”, 岩波書店, 2016.（Amazonアソシエイトリンク）

※この記事にはAmazonアソシエイトのリンクが含まれています。購入された場合、収益の一部を得ることがあります。

2.1. 流れ図 >>