完全二分木 vs 全二分木 vs 完璧二分木
完全（complete）二分木、全（full）二分木、完璧（perfect）二分木の違いを学びます。構造的な性質、ノード数の公式、各タイプが実際に使用される場面を理解します。
Properties
詳細な説明
二分木の種類
二分木にはノードの配置方法を記述するいくつかの構造的分類があります。
全二分木（Full Binary Tree）
すべてのノードが 0 または 2 の子 を持つ — 子がちょうど 1 つのノードはありません。
性質:
- リーフノード数 = 内部ノード数 + 1
- 総ノード数は常に奇数
完全二分木（Complete Binary Tree）
最後のレベルを除くすべてのレベルが完全に埋められ、最後のレベルは左から右に埋められます。
性質:
- 高さ = floor(log2(n))
- 配列に効率的に格納可能：インデックス i のノードに対し、左の子は 2i+1、右の子は 2i+2
- 二分ヒープは常に完全二分木
完璧二分木（Perfect Binary Tree）
すべてのレベルが完全に埋められている — 全二分木かつ完全二分木。すべてのリーフノードが同じレベル。
性質:
- 総ノード数 = 2^h - 1（h はノードを数えた高さ）
- リーフノード数 = 2^(h-1)
- すべてのリーフが同じ深さ
- 最も稀な形態 — 特定のノード数（1, 3, 7, 15, 31, ...）でのみ存在
退化木（Pathological Tree）
すべての内部ノードがちょうど 1 つの子を持つ — 実質的に連結リスト。高さがノード数に等しく、すべての木操作が O(n) に劣化します。
ユースケース
完全二分木は優先度キュー、ヒープソート、Dijkstra のアルゴリズムで使用される二分ヒープの基礎です。全二分木はデータ圧縮のハフマン符号化に現れます。完璧二分木は平衡木の理論的最良ケースを表し、トーナメント形式のアルゴリズムで使用されます。