特定の二分木がC++の赤黒木と同じように高さのバランスが取れているかどうかを確認します

/* This program to check whether a given Binary Tree is balanced like a Red-Black Tree or not */
#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);
}
/* Driver program to test above functions*/
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;
}

出力

Balanced