C++で高さhの平衡二分木（バランス木）の総数を求める方法

本記事では、二分木の高さHが与えられたとき、その高さを持つ平衡二分木（バランスの取れた二分木）が何通り存在するかをC++で求める方法を解説します。

二分木とは

二分木（バイナリツリー）とは、各ノードが最大2つの子ノード（左の子と右の子）を持つ木構造のデータ構造です。

高さ平衡二分木とは

高さ平衡二分木（height-balanced binary tree）とは、すべてのノードにおいて、左部分木と右部分木の深さの差が0または1しかない二分木として定義されます。つまり、どのノードを見ても、左部分木と右部分木の高さの差は最大で1である必要があります。

次の図は、高さh=3の場合に考えられる高さ平衡二分木の一例を示しています。

入力例1

Height H=2

出力例1

Count of Balanced Binary Trees of Height H is : 3

説明：次の図は、高さH=2の場合に存在しうる平衡二分木を示したものです。

入力例2

Height H=3

出力例2

Count of Balanced Binary Trees of Height H is : 15

アルゴリズムの考え方

• 整数Hは二分木の高さを表します。
• 関数countBTheight(int h)は木の高さを引数として受け取り、高さhとなる平衡二分木の総数を返します。
• ここでは再帰的なアプローチを採用します。
• 木の高さが0または1（ノードが1つだけ）の場合、存在する木は単一ノードの木のみであり、これは必ず平衡です。したがって if(h==0 || h==1) のとき return 1 となります。
• それ以外の場合、根の左右の部分木の高さは「根より1小さい」か「2小さい」のいずれかになります（平衡木では左右の高さの差が1以下であるため）。これらの組み合わせをすべて足し合わせることで、高さhの平衡二分木の総数が求まります。
• 関数は最終的に計算されたカウントを結果として返します。

漸化式のポイント

高さhの平衡二分木の総数をT(h)とすると、次の漸化式が成り立ちます。

T(h) = T(h-1) × ( T(h-1) + 2 × T(h-2) )

これは、「左がh-1・右がh-1」「左がh-1・右がh-2」「左がh-2・右がh-1」の3パターンの組み合わせをすべて考慮したものです。

C++による実装例

#include <iostream>
int countBTheight(int h){
   // 高さ0または1のとき、木は1通りしか存在しない
   if (h == 0 || h == 1)
      return 1;
   return countBTheight(h-1) * (2 * countBTheight(h-2) + countBTheight(h-1));
}
int main(){
   int H = 4;
   std::cout << "Count of balanced binary trees of height H is: " << countBTheight(H);
}

出力

Count of balanced binary trees of height H is: 315

このように、再帰と漸化式を利用することで、任意の高さHに対して平衡二分木の総数を効率的に求めることができます。なお、素朴な再帰実装では同じ値を何度も計算するため計算量が増大します。実用的にはメモ化（動的計画法）を併用すると、O(H)程度の時間で高速に求められます。