完全二分木とは？定義・性質・配列実装（ヒープ）と判定アルゴリズムをやさしく解説
エバープレイ編集部完全二分木とは — 基本定義と用語整理
完全二分木（かんぜんにぶんぎ、complete binary tree）は、二分木のうち特定の構造的な制約を満たす木構造です。もっとも一般的に使われる定義は「根から深さ0,1,2…とレベルを下ると、最下層（最後のレベル）を除いてすべてのレベルが完全に埋まっており、最下層のノードは左詰めで配置されている」というものです。
ここで用語の整理をしておきます。二分木に関して似た用語が複数あり、混同されやすいので注意が必要です。
- 完全二分木（complete binary tree）: 上述の通り、最後のレベルのみ未満の場合があり、そのノードは左詰めで配置される。
- 満たされた二分木（perfect binary tree / full & complete）: 全ての内部ノードがちょうど2つの子を持ち、全ての葉が同じ深さにある。ノード数は 2^{h+1}-1（hは高さ）で表される。
- 完全（full）/全二分木（binary tree with every node 0 or 2 children）: 文献によって呼び名が異なるが、一般には「各ノードが0か2個の子しか持たない」木を指すことがある。英語の "full" や "proper" の訳語が混在する。
構造的性質と基本公式
完全二分木は形が制約されているため、いくつかの便利な性質を持ちます。代表的なものを示します。
- 高さ（h）とノード数（n）の関係: 完全二分木の高さ（根を0とする）は h = floor(log2 n) です。逆に高さ h の完全二分木のノード数は最小で 2^h、最大で 2^{h+1}-1 です。
- 葉の個数: ノード数 n の完全二分木における葉の数は ceil(n/2) です。理由は配列表現で示すと分かりやすく、1..floor(n/2) のインデックスが内部ノード、残りが葉になるためです。
- 内部ノードの数: floor(n/2)。配列での見方と一致します（根を1とする1-basedインデックスで考える場合）。
- 満たされた二分木との関係: 完全二分木が最も密にノードを詰めたときは満たされた（perfect）二分木になり、その場合 n = 2^{h+1}-1 です。
配列による実装（ヒープの基礎）
完全二分木は配列で効率的に表現できます。これはヒープ（binary heap）などで一般的に使われる実装方法です。配列を使う利点はポインタを使うツリー実装に比べてメモリ効率とキャッシュ局所性が良い点です。
典型的なインデックス規約：
- 1-based（1から始まるインデックス）: 親(i) = floor(i/2), 左子 = 2i, 右子 = 2i+1。
- 0-based（0から始まるインデックス）: 親(i) = floor((i-1)/2), 左子 = 2i+1, 右子 = 2i+2。
この規約により、配列位置だけで親子の関係が直接計算でき、追加・削除（末尾追加→上に「浮上」、根削除→末尾を根に移して下に「沈める」）はインデックス計算だけで実行できます。
アルゴリズムと複雑度
完全二分木が登場する代表的なアルゴリズムと計算量です。
- ヒープ操作（優先度付きキュー）: 挿入（push）と削除（pop）は O(log n)。これは木の高さが O(log n) であり、要素の上昇／下降が高さ分のみ行われるためです。
- ヒープ構築（build-heap）: n個の要素からヒープを作る手法（下から沈める方法）では O(n) の時間で可能です。単純に逐次挿入すると O(n log n) だが、下からのheapifyを使うと線形時間になります（帰納的解析または完全二分木のレベル別解析で証明可能）。
- 探索や走査: 完全二分木は特定の検索木（BST）としての性質を持つわけではないので一般の探索は O(n)。ただし、レベル順（幅優先）走査は配列での実装と親子インデックスの関係により単純かつ高速に実行できます。
完全性の判定（レベル順走査によるアルゴリズム）
与えられた二分木が完全かどうかを O(n) 時間で判定する方法は簡単かつ実用的です。手順を概説します。
- レベル順（幅優先）でノードを列挙する。キューを用いる。
- ノードを取り出す際に、左子がないが右子がある場合は直ちに完全でないと判定（完全二分木ではあり得ない）。
- 左子または右子が欠けたノードを一度でも見つけたら「以降に子を持つノードが出現してはならない」というフラグを立てる。以後、取り出すノードで子を持つものが見つかれば非完全。
- 全ノードを確認して矛盾がなければ完全二分木である。
擬似コード（概念）:
flag = false
enqueue(root)
while queue not empty:
node = dequeue()
if node.left is null and node.right is not null:
return false
if flag and (node.left != null or node.right != null):
return false
if node.left == null or node.right == null:
flag = true
return true
応用例と実務での利用場面
完全二分木は実務でも頻繁に使われます。代表的な応用を挙げます。
- 優先度付きキュー（binary heap）: 最も典型的。配列での効率的表現と O(log n) の主要操作により、スケジューリングや Dijkstra、ヒープソートなどで広く使われます。
- セグメントツリーやフェノウィックツリー（BIT）: セグメントツリーは内部的にサイズを2のべき乗に切り上げ、完全二分木として表現することが多い。これにより区間クエリや区間更新が効率的になる。
- 配列ベースのツリー表現が有利な場面: メモリの連続領域を利用できるため、ポインタオーバーヘッドや断片化が嫌われる組み込み系やパフォーマンス重視の実装で採用される。
完全二分木と「平衡（balanced）」木の違い
完全二分木は非常に規則的な構造を持つため高さが低く抑えられますが、「平衡二分探索木」（AVL木や赤黒木など）とは用途や保証が異なります。
- 完全二分木: 構造的に高さは floor(log2 n) と小さいが、ノードがキー順に並ぶという保証はない（BSTの条件を満たす必要がない）。
- 平衡二分探索木: 検索・挿入・削除に対して常に O(log n) を保証するが、構造は完全ではない。BSTの順序性（キーの大小関係）を保持する点が特徴。
実装上の注意点と落とし穴
実務で完全二分木（特に配列表現）を扱う際に注意すべき点を列挙します。
- インデックスの規約（0-basedか1-basedか）をプロジェクトで統一する。誤った規約はバグの温床になります。
- サイズを2のべき乗に合わせる実装（セグメントツリーなど）では、余分なパディングが発生する。メモリトレードオフを考慮する。
- 完全性の定義を確認する。文献や教材によって「満たされた二分木」との呼称のずれがあるため、要件定義で用語を明確にしておく。
- ヒープを用いるアルゴリズムでは安定性（同値キーの順序保持）が保証されない点に注意。安定性が必要な場合は別のデータ構造を検討する。
理論的な補足：ノード数と高さの証明的事実
いくつかの簡単な証明的事実を示しておきます（直感的な説明中心）。
- 高さ h の満たされた二分木のノード数は 1 + 2 + 4 + ... + 2^h = 2^{h+1}-1。これは各レベルのノード数が等比数列になっているためです。
- ノード数 n に対して高さ h が floor(log2 n) である理由: レベル0からh-1までは合計で 2^h-1 個のノードが配置でき、最下層に少なくとも1個、最大2^h個のノードが配置できるため、2^h ≤ n ≤ 2^{h+1}-1。これを対数で解くと h = floor(log2 n) になります。
- 葉の数が ceil(n/2) である理由: 配列表現で見ると、1..floor(n/2) が子を持つ可能性のあるノード（内部ノード）で、残りが葉になるからです。
まとめ
完全二分木は「ほぼ満点」に近い形でノードが詰まっている二分木で、配列表現に非常に適しているため実装コストと実行速度の面で有利です。ヒープやセグメントツリーなど多くのアルゴリズムで基盤となる構造であり、その性質（高さ、インデックス関係、葉・内部ノード数）を押さえておくことは開発やアルゴリズム設計で重要です。
参考文献
- 完全二分木 - Wikipedia（日本語）
- Complete binary tree - Wikipedia（English）
- Binary heap - Wikipedia（English）
- ヒープ (データ構造) - Wikipedia（日本語）
投稿者プロフィール
