C++で完全二分木の全ノードの合計を効率的に求める方法

問題の概要

正整数 L が与えられ、これは完全二分木（パーフェクト・バイナリツリー）のレベル数を表しているとします。この木の葉ノードには、1 から n までの番号が順に割り当てられています（n は葉ノードの総数）。また、各親ノードの値は、その 2 つの子ノードの値の合計となります。

今回の課題は、この完全二分木に含まれるすべてのノードの値の合計を出力するプログラムを作成することです。

例として、次のような木を考えてみましょう。

この木の場合、すべてのノードの合計は 30 になります。

解法のアプローチ

この問題を注意深く観察すると、求めるべきは全ノードの値の総和です。葉ノードには 1 から n までの連続した整数が格納されているため、等差数列の和の公式 n(n+1)/2 を使えば、葉ノードの合計を簡単に計算できます。

さらに重要な性質として、完全二分木では各レベルのノードの値の合計が必ず等しくなるという点が挙げられます。これは「親ノードの値 = 子ノード 2 つの値の合計」というルールから導かれるもので、あるレベルの合計は、その直下のレベルの合計と必ず一致します。

したがって、以下の手順で答えを求められます。

1. 葉ノードの総数 n を 2^(L-1) で計算する（L はレベル数）
2. 葉ノードの合計を n(n+1)/2 の公式で求める
3. その合計にレベル数 L を掛けた値が、全ノードの合計となる

C++での実装例

#include<iostream>
#include<cmath>
using namespace std;
int treeSum(int level) {
   int total_leaves = pow(2, level - 1);   // 葉ノードの総数
   int leaf_sum = (total_leaves * (total_leaves + 1)) / 2;   // 葉ノードの合計
   int sum = leaf_sum * level;   // 各レベルの合計が等しいため、レベル数を掛ける
   return sum;
}
int main() {
   int levels = 4;
   cout << "レベル " << levels << " の完全二分木の全ノードの合計: " << treeSum(levels);
}

実行結果

レベル 4 の完全二分木の全ノードの合計: 144

計算量の評価

この解法は pow 関数と四則演算のみで構成されているため、時間計算量は O(1) です。つまり、木のサイズに関わらず一定時間で答えを求められます。実際に木を構築して全ノードを走査する方法（O(n)）と比較しても、非常に効率的なアプローチだと言えるでしょう。