ধারণা
একটি লাল-কালো গাছের ক্ষেত্রে, একটি নোডের বৃহত্তম উচ্চতা সর্বনিম্ন উচ্চতার দ্বিগুণ হয়৷ একটি প্রদত্ত বাইনারি অনুসন্ধান গাছের জন্য, আমাদের নিম্নলিখিত সম্পত্তির জন্য যাচাই করতে হবে৷
প্রতিটি নোডের ক্ষেত্রে, দীর্ঘতম পাতা থেকে নোড পথের দৈর্ঘ্য নোড থেকে পাতা পর্যন্ত সংক্ষিপ্ততম পথে নোডের দ্বিগুণের বেশি নয়।
উদাহরণ
13 41 \ / \ 15 11 101 \ / \ 17 61 151
উপরের গাছটি লাল-কালো গাছ হতে পারে না উপরের গাছটি যে কোনও রঙের অ্যাসাইনমেন্ট সহ লাল-কালো গাছ হতে পারে
13 এর সর্বোচ্চ উচ্চতা হল 1
13 এর সর্বনিম্ন উচ্চতা 3
11 / \ 6 101 / \ 51 151 / 41
উপরের গাছটি লাল-কালো গাছও হতে পারে
এই ক্ষেত্রে, প্রত্যাশিত সময়ের জটিলতা হল O(n)। দ্রবণে গাছটিকে একবারে পরিদর্শন করা উচিত।
পদ্ধতি
প্রতিটি নোডের সম্মানের সাথে, আমাদের সবচেয়ে বড় এবং ক্ষুদ্রতম উচ্চতা পেতে হবে এবং তাদের তুলনা করতে হবে। ধারণাটি হল গাছটি পরিদর্শন করা এবং প্রতিটি নোডের জন্য এটি ভারসাম্যপূর্ণ কিনা তা যাচাই করা। আমাদের প্রয়োজন একটি পুনরাবৃত্ত ফাংশন লিখতে যা তিনটি জিনিস প্রদান করে, একটি বুলিয়ান মান নির্দেশ করে যে গাছটি ভারসাম্যপূর্ণ কি না, ক্ষুদ্রতম উচ্চতা এবং বৃহত্তম উচ্চতা। একাধিক মান ফেরত দেওয়ার জন্য, আমরা হয় একটি কাঠামো প্রয়োগ করতে পারি বা রেফারেন্সের মাধ্যমে ভেরিয়েবল পাস করতে পারি৷ ম্যাক্স এবং মিনহবি রেফারেন্স পাস করা হয় যাতে অভিভাবক কলগুলিতে মানগুলি প্রয়োগ করা যায়৷
উদাহরণ
/* 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
