C++で特定の二分木が赤黒木と同じように高さバランスされているかを判定する方法

概念

赤黒木（Red-Black Tree）では、あるノードにおける最大高さは、最小高さの2倍以下でなければなりません。したがって、与えられた二分探索木に対して、以下の性質を満たしているかどうかを検証する必要があります。

検証すべき性質： すべてのノードについて、そのノードから最も遠い葉までの経路（最長経路）に含まれるノード数が、最も近い葉までの経路（最短経路）に含まれるノード数の2倍を超えないこと。

例1：赤黒木になれないケース

13    41
\    / \
15  11 101
\   /    \
17 61 151

この木の場合、ノード13の最大高さは1、最小高さは3です。最大高さが最小高さの2倍を超えているため、どのような色の割り当てを行っても赤黒木にはなり得ません。

例2：赤黒木になれるケース

   11
  / \
 6   101
 /    \
51    151
/
41

この木は、適切な色の割り当てによって赤黒木として成立し得ます。

なお、本問題で期待される時間計算量は O(n) であり、解法の中で木全体を多くとも一度だけ訪問する必要があります。

アルゴリズムの考え方

各ノードについて最大高さと最小高さを取得し、両者を比較します。基本的なアプローチは、木を巡回しながら、すべてのノードがバランス条件を満たしているかを順に確認していくことです。

具体的には、以下の3つの情報を返す再帰関数を作成します。

• 木がバランスしているかどうかを示すブール値
• 部分木の最小高さ
• 部分木の最大高さ

複数の値を返す方法としては、構造体を使用する方法と、変数を参照渡しで渡す方法があります。ここでは maxh（最大高さ）と minh（最小高さ）を参照渡しすることで、親の再帰呼び出し側でもこれらの値を利用できるようにしています。

C++での実装例

/* 与えられた二分木が赤黒木のようにバランスしているかを判定するプログラム */
#include <bits/stdc++.h>
using namespace std;
struct Node1{
   int key;
   Node1 *left, *right;
};
Node1* newNode(int key){
   Node1* node1 = new Node1;
   node1->key = key;
   node1->left = node1->right = NULL;
   return (node1);
}
bool isBalancedUtil(Node1 *root, int &maxh1, int &minh1){
   if (root == NULL){
      maxh1 = minh1 = 0;
      return true;
   }
   int lmxh1, lmnh1;
   int rmxh1, rmnh1;
   if (isBalancedUtil(root->left, lmxh1, lmnh1) == false)
      return false;
   if (isBalancedUtil(root->right, rmxh1, rmnh1) == false)
      return false;
   maxh1 = max(lmxh1, rmxh1) + 1;
   minh1 = min(lmnh1, rmnh1) + 1;
   if (maxh1 <= 2*minh1)
      return true;
   return false;
}
bool isBalanced(Node1 *root){
   int maxh1, minh1;
   return isBalancedUtil(root, maxh1, minh1);
}
/* 動作確認用のドライバープログラム */
int main(){
   Node1 * root = newNode(11);
   root->left = newNode(6);
   root->right = newNode(101);
   root->right->left = newNode(51);
   root->right->right = newNode(151);
   root->right->left->left = newNode(41);
   isBalanced(root)? cout << "Balanced" : cout << "Not Balanced";
   return 0;
}

コードのポイント

• ベースケース： ノードがNULLの場合、高さは0とし、バランスしているとみなして true を返します。
• 再帰処理： 左右の子部分木それぞれに対して再帰的に判定を行い、どちらか一方でもバランスしていなければ即座に false を返します。
• 高さの更新： 子部分木の結果をもとに、現在のノードの最大高さ・最小高さを計算します。
• バランス判定： 最大高さが最小高さの2倍以下であれば true、そうでなければ false を返します。

出力

Balanced

この実装では、木の各ノードをちょうど一度だけ訪問するため、時間計算量はO(n)、再帰によるスタック使用を含め空間計算量は木の高さに比例してO(h)となります。