কনসেপ্ট
রেড-ব্ল্যাক ট্রিতে একটি নোডের সর্বোচ্চ হাইট তার ন্যূনতম হাইটের আটকা দ্বিগুণ হতে পারে। একটি বাইনারি সার্চ ট্রি দিয়ে এই প্রপার্টি যাচাই করুন: প্রতিটি নোডের জন্য, লংগেস্ট লিফ-টু-নোড পাথের দৈর্ঘ্য শর্টেস্ট পাথের দৈর্ঘ্যের দ্বিগুণের চেয়ে বেশি নয়।
উদাহরণ
13 41 \ / \ 15 11 101 \ / \ 17 61 151
উপরের ট্রি রেড-ব্ল্যাক ট্রি হতে পারে না। নিচের ট্রি হতে পারে।
11 / \ 6 101 / \ 51 151 / 41
সময় জটিলতা O(n)। ট্রি সর্বোচ্চ একবার ভিজিট করতে হবে।
পদ্ধতি
প্রতিটি নোডের জন্য সর্বোচ্চ ও ন্যূনতম হাইট বের করে তুলনা করুন। রিকার্সিভ ফাংশন লিখুন যা তিনটি জিনিস রিটার্ন করবে: ব্যালেন্সড কিনা (bool), ন্যূনতম হাইট (minh), সর্বোচ্চ হাইট (maxh)। রেফারেন্স দিয়ে maxh এবং minh পাস করুন যাতে প্যারেন্ট কলগুলোও ব্যবহার করতে পারে।
উদাহরণ
#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;
} আউটপুট
Balanced
