分野 ：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：データ構造

葉以外のすべての節点がすべての子を持ち、根から葉までの深さがすべて等しい2分木を完全2分木といいます。

この木構造において深さ(k)が増加すると節点数(n)は次のように変化していきます。

• k＝1→n＝3
• k＝2→n＝7
• k＝3→n＝15
• k＝4→n＝31

ここでは選択肢の式にk＝3を代入して、nが15になるか否かで適切な式を導きます。

• 3(3＋1)＋1＝12＋1＝13(×)
• 2³＋3＝8＋3＝11(×)
• 2³⁺¹－1＝16－1＝15(○)
• (3－1)(3＋1)＋4＝8＋4＝12(×)

したがって節点数と深さの関係を表す式は「n＝2^k＋1－1」になります。