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

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

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

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

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

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

💾 ✔️