ホーム
技術解説

２分木を理解する

1. 木構造について

　２分木について理解する前に、まずは木構造について確認していきます。

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

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

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

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

  • 根（ルート）：木の最上位に位置するノード
  • 枝（エッジ）：ノード間を接続する線
  • 葉（リーフ）：子ノードを持たない末端ノード
  • 内部ノード：葉ではないノード（子を持つノード）
  • 親ノード：あるノードに対して上位に接続されているノード
  • 子ノード：あるノードから枝で接続された下位のノード
  • 兄弟：同じ親を持つノード同士
  • 深さ：根からあるノードまでの経路の長さ
  • 高さ：木の最も深い部分の深さ
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: 木構造の基本用語

　ここまでの内容は、以下の「1.2.4. 木構造」にて解説しています。

1.2.4. 木構造
木構造の種類と考え方，木の巡回法，節の追加や削除，ヒープの再構成などを理解する。根，葉，枝，2 分木，完全2 分木，バランス木，順序木，多分木，探索木，2 分探索木，B木，AVL木，深さ優先探索，幅優先探索，先行順，後行順，中間順
tech.itq.co.jp

3. ２分木とは

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

　今回の解説は、この２分木についてです。２分木には、主に次の３種類があります。

3.1. 完全2分木 (Complete Binary Tree)

  • 定義：最下層を除くすべての層が完全に埋まっており、最下層は左から順に埋まっている
  • 特徴：
    • 最下層以外の各ノードは必ず2つの子を持つ
    • 最下層は左から右へ連続して詰めて埋められている（途中に空きがない）
    • 右側に空きがあってもよい
  • 用途：ヒープデータ構造として配列実装しやすい

3.2. 満杯2分木 (Full Binary Tree)

  • 定義：すべての内部ノードが正確に2つの子を持つ木（子を持つノードは必ず2つの子を持つ）
  • 特徴：
    • 各ノードは0個または2個の子を持つ（1つだけ子を持つノードは存在しない）
    • 葉ノードの深さは異なる場合がある
  • 用途：式の表現や決定木など

3.3. 完璧2分木 (Perfect Binary Tree)

  • 定義：すべての内部ノードが2つの子を持ち、すべての葉が同じ深さにある
  • 特徴：
    • 最も厳格な2分木の形式
    • すべての層が完全に埋まっている
    • ノード数が2^h – 1（hは高さ）になる
  • 用途：トーナメント構造、完全バランス探索など

3.4. 違いのわかりやすい例

  • 完全2分木：最下層以外はすべて2つの子を持ち、最下層は左詰め
  • 満杯2分木：子を持つノードは必ず2つの子を持つが、葉の深さは揃っていなくてもよい
  • 完璧2分木：すべてのノードが規則正しく配置され、完全に対称的な構造
graph TD
    subgraph "完全二分木 (Complete Binary Tree)"
        A1[1] --> B1[2]
        A1 --> C1[3]
        B1 --> D1[4]
        B1 --> E1[5]
        C1 --> F1[6]
        C1 --> G1[7]
        D1 --> H1[8]
        D1 --> I1[9]
        E1 --> J1[10]
    end

    subgraph "満杯二分木 (Full Binary Tree)"
        A2[1] --> B2[2]
        A2 --> C2[3]
        B2 --> D2[4]
        B2 --> E2[5]
        C2 --> F2[6]
        C2 --> G2[7]
    end

    subgraph "完璧二分木 (Perfect Binary Tree)"
        A3[1] --> B3[2]
        A3 --> C3[3]
        B3 --> D3[4]
        B3 --> E3[5]
        C3 --> F3[6]
        C3 --> G3[7]
    end

図２：完全２分木、満杯２分木、完璧２分木の比較図

　これだけだと、わかりにくいところもありますので例を示します。

　右のような完全２分木について、「１０」のノードを削除すると左のようになり、満杯２分木となります。葉の高さは揃っていませんが、子を持つノードはすべて０または２つのノードを持っています。（子が１のノードはありません）

graph TD
    subgraph "元の完全二分木 (Complete Binary Tree)"
        A1[1] --> B1[2]
        A1 --> C1[3]
        B1 --> D1[4]
        B1 --> E1[5]
        C1 --> F1[6]
        C1 --> G1[7]
        D1 --> H1[8]
        D1 --> I1[9]
        E1 --> J1[10]
    end

    subgraph "ノード10を削除後（満杯二分木になる）"
        A2[1] --> B2[2]
        A2 --> C2[3]
        B2 --> D2[4]
        B2 --> E2[5]
        C2 --> F2[6]
        C2 --> G2[7]
        D2 --> H2[8]
        D2 --> I2[9]
    end

図３：完全２分木から満杯２分木へ

　さらに「８」「９」を削除すると、完璧２分木となります。高さも揃って、完全に対象な形となり、完璧２分木です。

graph TD
    subgraph "元の完全二分木 (Complete Binary Tree)"
        A1[1] --> B1[2]
        A1 --> C1[3]
        B1 --> D1[4]
        B1 --> E1[5]
        C1 --> F1[6]
        C1 --> G1[7]
        D1 --> H1[8]
        D1 --> I1[9]
        E1 --> J1[10]
    end

    subgraph "ノード8,9,10を削除後（完璧二分木になる）"
        A2[1] --> B2[2]
        A2 --> C2[3]
        B2 --> D2[4]
        B2 --> E2[5]
        C2 --> F2[6]
        C2 --> G2[7]
    end

図４：完全２分木と完璧２分木

　さて、ここまでの説明だと「完璧２分木は、満杯２分木のサブセット？高さが揃えば、満杯２分木は完璧２分木？」と思えてしまいますが、そうではありません。以下にその例を示します。

graph TD
    subgraph "満杯二分木だが完全二分木ではない例"
        A1[1] --> B1[2]
        A1 --> C1[3]
        C1 --> F1[6]
        C1 --> G1[7]
    end

    subgraph "完全二分木だが満杯二分木ではない例"
        A2[1] --> B2[2]
        A2 --> C2[3]
        B2 --> D2[4]
        B2 --> E2[5]
        C2 --> F2[6]
    end

    subgraph "両方の条件を満たす例（完璧二分木）"
        A3[1] --> B3[2]
        A3 --> C3[3]
        B3 --> D3[4]
        B3 --> E3[5]
        C3 --> F3[6]
        C3 --> G3[7]
    end

図５：完璧２分木と満杯２分木と完全２分木

  1. 満杯二分木だが完全二分木ではない例：
    • 各ノードは0個または2個の子を持つので満杯二分木
    • しかし、左側（ノード2の下）に子がないのに右側（ノード3の下）に子がある
    • これは「左から詰める」という完全二分木の条件に違反
  2. 完全二分木だが満杯二分木ではない例：
    • 最後のレベル以外は完全に埋まっており、最後のレベルは左から詰められているので完全二分木
    • しかし、ノード3が子を1つだけ（ノード6）持っている
    • これは「0個または2個の子を持つ」という満杯二分木の条件に違反
  3. 両方の条件を満たす例：
    • 完璧二分木は両方の条件を同時に満たしている

　満杯二分木が「各ノードが0個または2個の子を持つ」という条件に注目していることに対し、完全二分木は「最後のレベルを除くすべてのレベルが完全に埋まっている」かつ「最後のレベルは左から詰めて配置される」という、ノードの配置パターンに注目しています。

　今回の例で見たように、満杯二分木では「左から詰める」という制約がないため、左側に子がなくても右側に子を持つことができます。これが完全二分木の条件を満たさない理由となります。

　二分木の種類を理解する際には、これらの定義の微妙な違いを把握することが重要です。特にアルゴリズムやデータ構造を扱う際には、それぞれの特性を活かした実装が必要になることがあります。

4. まとめ

　今回は、完全２分木、満杯２分木、完璧２分木についてみてきました。これらについて実務で深く突っ込むことはあまり多くないかと思いますが、このような違いのある間違えやすい用語があることから、齟齬が生じやすいところかと思います。

　迷ったときにはこの記事を思い出して再確認していただければ幸甚です。