अवधारणा
रेड-ब्लैक ट्री के संबंध में, एक नोड की अधिकतम ऊंचाई न्यूनतम ऊंचाई से अधिकतम दोगुनी होती है। दिए गए बाइनरी सर्च ट्री के लिए, हमें निम्नलिखित गुण की जांच करनी होगी: प्रत्येक नोड के लिए, नोड से लीफ तक के सबसे लंबे पथ की लंबाई, नोड से लीफ तक के सबसे छोटे पथ पर नोड्स की संख्या से दोगुनी से अधिक नहीं होनी चाहिए।
उदाहरण
13 41 \ / \ 15 11 101 \ / \ 17 61 151
ऊपर का ट्री रेड-ब्लैक ट्री नहीं हो सकता।
11 / \ 6 101 / \ 51 151 / 41
ऊपर का ट्री किसी भी रंग असाइनमेंट के साथ रेड-ब्लैक ट्री हो सकता है।
इस मामले में, अपेक्षित समय जटिलता O(n) है। ट्री को समाधान में अधिकतम एक बार देखा जाना चाहिए।
विधि
प्रत्येक नोड के लिए, हमें अधिकतम और न्यूनतम ऊंचाई प्राप्त करने और उनकी तुलना करने की आवश्यकता है। विचार ट्री को पार करना है और प्रत्येक नोड के लिए जांचना है कि क्या यह संतुलित है। हमें एक पुनरावर्ती फ़ंक्शन लिखना होगा जो तीन चीजें लौटाता है: एक बूलियन मान जो दर्शाता है कि ट्री संतुलित है या नहीं, न्यूनतम ऊंचाई और अधिकतम ऊंचाई। कई मान लौटाने के लिए, हम या तो एक संरचना का उपयोग कर सकते हैं या चर को संदर्भ द्वारा पास कर सकते हैं। maxh और minh को संदर्भ द्वारा पास किया जाता है ताकि मानों का उपयोग पैरेंट कॉल में किया जा सके।
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);
}
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