जांचें कि क्या दिया गया बाइनरी ट्री सी ++ में रेड-ब्लैक ट्री की तरह ऊंचाई संतुलित है

अवधारणा

रेड-ब्लैक ट्री के संबंध में, नोड की सबसे बड़ी ऊंचाई न्यूनतम ऊंचाई से अधिक से अधिक दोगुनी है। किसी दिए गए बाइनरी सर्च ट्री के लिए, हमें निम्नलिखित संपत्ति के लिए सत्यापित करने की आवश्यकता है।

प्रत्येक नोड के संबंध में, सबसे लंबी पत्ती से नोड पथ की लंबाई नोड से पत्ती तक के सबसे छोटे पथ पर दोगुने से अधिक नहीं है।

उदाहरण

ऊपर का पेड़ लाल-काले पेड़ नहीं हो सकता ऊपर का पेड़ किसी भी रंग असाइनमेंट के साथ लाल-काला पेड़ हो सकता है

13 की अधिकतम ऊंचाई 1

. है

13 की न्यूनतम ऊंचाई 3 है

ऊपर का पेड़ लाल-काला पेड़ भी हो सकता है

इस मामले में, अपेक्षित समय जटिलता ओ (एन) है। घोल में पेड़ को कम से कम एक बार जरूर देखना चाहिए।

विधि

प्रत्येक नोड के संबंध में, हमें सबसे बड़ी और सबसे छोटी ऊंचाई प्राप्त करने और उनकी तुलना करने की आवश्यकता होती है। अवधारणा पेड़ का दौरा करना है और प्रत्येक नोड के लिए सत्यापित करना है कि यह संतुलित है या नहीं। हमारी आवश्यकता एक पुनरावर्ती कार्य लिखने की है जो तीन चीजें लौटाता है, एक बूलियन मान इंगित करता है कि पेड़ संतुलित है या नहीं, सबसे छोटी ऊंचाई और सबसे बड़ी ऊंचाई। एकाधिक मान वापस करने के लिए, हम या तो संरचना लागू कर सकते हैं या संदर्भ द्वारा चर पास कर सकते हैं। अधिकतम और minhby संदर्भ पास करना ताकि मूल्यों को मूल कॉल में लागू किया जा सके।

उदाहरण

/* 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