完全二分木とは？かんぜんにぶんぎ
完全二分木とは、根から最後の1つ手前のレベルまで全ての節が2個の子を持ち、最下位レベルは左から詰めて配置されている二分木。段数（高さ）がlog₂n程度に抑えられる（データが2倍になっても段数は1つ増えるだけ）ため、ヒープ（親が子より常に大きい、または常に小さい値を持つ木）への挿入や最大値・最小値の取出しのように根から葉まで1本の道をたどる処理はO(log n)（データが増えても手間は段数ぶんしか伸びない）で済む。ただし形の決まりだけで値の大小の並びは決めないので、任意の値を探す処理が速くなるわけではない。ヒープはこの形を保つことで配列に隙間なく格納できる。
最終更新：2026-10-09
基本情報を最短で暗記・合格する →具体例
節数nの完全二分木は、根を添字1として配列に並べると、添字iの節の左の子は2i、右の子は2i+1、親は i÷2 の整数部分で求まる。ポインタを使わずに親子をたどれるため、ヒープソートの実装が配列だけで完結する。
試験での引っ掛け
最下位レベルは「左から詰まっている」ことが条件で、途中が空いていれば完全二分木ではない。また添字を0から始めると子の位置は2i+1、2i+2に変わるため、問題の添字の起点を必ず確認する。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。