完全2分木とは？定義・ノード数の公式・配列表現・判定アルゴリズムをわかりやすく解説
エバープレイ編集部完全2分木とは — 概要と定義
完全2分木（かんぜんにぶんぎ/perfect binary tree）は、二分木のうちで「すべての葉が同じ深さにあり、かつ全ての内部ノードがちょうど2つの子を持つ」ものを指します。日本語で「完全」「満たされた」などと訳されることがあり、英語では perfect binary tree と呼ばれます。
定義のポイント
- すべての内部ノード（子を持つノード）はちょうど2つの子を持つ。
- すべての葉ノードは同一の深さ（高さ）に存在する。
- ある高さ（深さ）h の完全2分木は、各レベル 0 から h までが完全に埋まっている構造である。
ノード数と高さの関係（基本公式）
高さ h の完全2分木（根の深さを 0 とする場合）に含まれるノード数 n は次の式で表されます。
n = 2^(h+1) − 1
葉の数 L（最下層のノード数）は
L = 2^h
内部ノードの数 I（葉以外のノード数）は
I = n − L = 2^h − 1
これらは等比数列の和の公式（1 + 2 + 4 + ... + 2^h = 2^(h+1) − 1）から容易に導かれます。
高さとノード数の逆変換
ノード数 n が与えられたとき、完全2分木であることが前提ならば高さ h は次の式で得られます。
2^(h+1) = n + 1 → h = log2(n + 1) − 1
したがって、n+1 が 2 のべき乗でない限り、その n に対応する完全2分木は存在しません（完全であるためには n+1 が 2 のべき乗である必要がある）。
配列による表現（添字の取り方）
完全2分木は全てのレベルが埋まっているため、ノードを配列に連続して格納するのに向いています。インデックスの取り方には主に 1 始まりと 0 始まりの2通りがあります。
- 1始まりのインデックス i の場合：
- 左の子 = 2i
- 右の子 = 2i + 1
- 親 = floor(i / 2)（i > 1）
- 0始まりのインデックス i の場合：
- 左の子 = 2i + 1
- 右の子 = 2i + 2
- 親 = floor((i − 1) / 2)（i > 0）
この配列表現はヒープ（binary heap）や固定サイズの完全木を扱うときに計算量と空間効率の観点で有利です。ただしヒープは“完全（complete）”であって必ずしも“完全（perfect）”とは限らない点に注意してください（後述）。
完全2分木と他の二分木の用語の違い
- 完全（perfect）2分木：すべての葉が同じ深さ、内部ノードはちょうど2子を持つ。
- 満たされた（full）2分木：全てのノードが 0 または 2 の子を持つ（すべての内部ノードが2子）。完全(perfect)は満たされた木でもあり得ますが、満たされた木の葉は必ず同深とは限らない。
- 完全（complete）2分木：最後のレベル以外はすべて埋まっており、最後のレベルのノードは左詰めで配置される。ヒープはこの「complete」が要求される。
- 平衡（balanced）木：各部分木の高さ差などに制約がある木（AVLや赤黒木など）。完全2分木は最高にバランスの取れた形の一つ。
性質と導出（証明のスケッチ）
ノード数 n = 2^(h+1) − 1 の導出は帰納法や等比数列の和で示せます。レベル d（根を 0 とする）には 2^d 個のノードが存在するので、合計は sum_{d=0}^{h} 2^d = 2^{h+1} − 1 です。
また、「すべての葉の深さが同じ」かつ「内部ノードが2子持ち」であれば各レベルが完全に埋まることから上の等式が成り立ちます。
経路長・深さの合計（内部パス長）の式
完全2分木における全ノードの深さの合計 S（各ノードの深さを足し合わせた値）は次の式で表されます。
S = sum_{d=0}^{h} d * 2^d
この和は閉形式で表せ、既知の恒等式を使うと：
S = (h − 1) * 2^{h+1} + 2
ここで 2^{h+1} = n + 1 を代入すると S = (h − 1)(n + 1) + 2 となります。平均深さ（各ノードの平均レベル）は S / n で求められ、h が大きい場合は平均深さはおおむね h − 1 に近づきます。
アルゴリズム的利用例
- トーナメントツリー（勝ち残り形式の集計）や決定木での理想構造。
- 分割統治アルゴリズムの理論解析のモデル（完全に均等分割される理想ケース）。
- 配列ベースでの効率的な格納が可能なため、固定サイズで高さが決まる構造の実装に向く。
- セグメントツリーやフェニックスト木（Fenwick tree）は一般に「完全」や「満たされた」構造を利用するが、実運用ではノード数が 2 のべき乗に合わせるためにパディングして「ほぼ完全」な形にすることが多い（真の完全2分木にするためにはノード数が 2^{k} − 1 である必要がある）。
完全2分木の判定方法（アルゴリズム）
ある二分木が完全2分木かどうかを判定する方法はいくつかあります。
- ノード数と高さを数え、n = 2^{h+1} − 1 かをチェックする。これは最も簡単で確実。ただし高さの定義を一致させることを忘れない。
- 再帰的判定：木が空なら真。根が葉かつ深さが期待値なら真。内部ノードは両側に子があること、および左右の部分木が同一の高さかつともに完全であることを再帰的に確かめる。
- レベル順（BFS）で探索し、途中で「欠損ノード」を検出した後に再びノードが現れたら false とするような complete（完全）判定とは異なり、perfect 判定は葉の深さの均一性と全内部ノードが2子持ちであることを直接確認する。BFSで最下層以外がすべて埋まっているか確認することでも判定可能。
完全2分木と実用上の注意点
- 完全2分木は理想的な形だが、実世界のデータや操作（挿入・削除・不均一な分割）では常に保てるわけではない。挿入・削除の操作が頻繁な場合は、AVL木や赤黒木のような平衡二分探索木の方が柔軟性がある。
- ヒープは complete binary tree（完全木）を配列で表すが、完全（perfect）になるのはノード数がちょうど 2^{k} − 1 のときだけである。したがって「ヒープ＝完全2分木」と混同しないこと。
- メモリ配置は配列格納で非常に効率的だが、ノードが可変だったり部分木を頻繁に切り離すような用途にはポインタベースの表現が適する。
よくある誤解と混同
- 「完全（perfect）」と「完全（complete）」の訳語が日本語で同じ「完全」になって混乱することがあります。英語では perfect と complete は別概念なので注意してください。
- 「満たされた（full）」と「perfect」を混同する例もあります。full は「各ノードが 0 または 2 子」だが葉の深さは揃っていない場合がある。一方 perfect は全ての葉が同じ深さであり、必然的に full でもあります。
まとめ
完全2分木は理論解析や特定用途（配列格納が有利な場合、理想的な分割モデルなど）で重要な概念です。全ノード数が 2^{h+1} − 1 という明確な関係式を持ち、すべての葉が同じ深さにあるという強い制約から解析が容易になります。一方で現実のデータ構造設計では、挿入や削除を伴う操作の下では完全構造を維持するコストが高く、用途に応じて complete や balanced な木と使い分けることが一般的です。
参考文献
- Perfect binary tree — Wikipedia
- Perfect Binary Tree (GeeksforGeeks)
- Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms (教科書的参考)
- What is the difference between a full, complete and perfect binary tree? — CS Stack Exchange
投稿者プロフィール
