完全二分木とは？

完全二分木とは、根から最後の1つ手前のレベルまで全ての節が2個の子を持ち、最下位レベルは左から詰めて配置されている二分木。高さがlog₂n程度に抑えられるため、探索や更新をO(log n)で行える。ヒープはこの形を保つことで配列に隙間なく格納できる。

かんぜんにぶんぎ

基本情報技術者試験の頻出用語／テクノロジ系

完全二分木の意味

根から最後の1つ手前のレベルまで全ての節が2個の子を持ち、最下位レベルは左から詰めて配置されている二分木。高さがlog₂n程度に抑えられるため、探索や更新をO(log n)で行える。ヒープはこの形を保つことで配列に隙間なく格納できる。

節数nの完全二分木は、根を添字1として配列に並べると、添字iの節の左の子は2i、右の子は2i+1、親は i÷2 の整数部分で求まる。ポインタを使わずに親子をたどれるため、ヒープソートの実装が配列だけで完結する。

最下位レベルは「左から詰まっている」ことが条件で、途中が空いていれば完全二分木ではない。また添字を0から始めると子の位置は2i+1、2i+2に変わるため、問題の添字の起点を必ず確認する。

最終更新：2026-08-25／解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。