Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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

अवधारणा

रेड-ब्लैक ट्री के संबंध में, एक नोड की अधिकतम ऊंचाई न्यूनतम ऊंचाई से अधिकतम दोगुनी होती है। दिए गए बाइनरी सर्च ट्री के लिए, हमें निम्नलिखित गुण की जांच करनी होगी: प्रत्येक नोड के लिए, नोड से लीफ तक के सबसे लंबे पथ की लंबाई, नोड से लीफ तक के सबसे छोटे पथ पर नोड्स की संख्या से दोगुनी से अधिक नहीं होनी चाहिए।

उदाहरण

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
  1. C++ में जांचें कि बाइनरी ट्री किसी अन्य बाइनरी ट्री का सबट्री है या नहीं C++ में जांचें कि बाइनरी ट्री किसी अन्य बाइनरी ट्री का सबट्री है या नहीं

    मान लीजिए हमारे पास दो बाइनरी ट्री हैं। हमें जांचना है कि छोटा ट्री दूसरे बाइनरी ट्री का सबट्री है या नहीं। मान लीजिए ये दो ट्री दिए गए हैं।दो ट्री हैं। दूसरा ट्री पहले का सबट्री है। इस गुण की जांच करने के लिए, हम ट्री को पोस्ट-ऑर्डर फैशन में ट्रैवर्स करेंगे, फिर यदि इस नोड से रूटेड सबट्री दूसरे ट्र

  1. C++ में जांचें कि बाइनरी ट्री लेवल-वार सॉर्टेड है या नहीं C++ में जांचें कि बाइनरी ट्री लेवल-वार सॉर्टेड है या नहीं

    यहां हम देखेंगे कि बाइनरी ट्री लेवल-वार सॉर्टेड है या नहीं, इसकी जांच कैसे करें। लेवल-वार सॉर्टेड बाइनरी ट्री नीचे जैसा दिखेगा -प्रत्येक लेवल में, नोड्स बाएं से दाएं सॉर्टेड होते हैं, और प्रत्येक लेयर में अपने पिछले लेवल से अधिक मान होता है।हम इस समस्या को लेवल ऑर्डर ट्रैवर्सल करके हल कर सकते हैं, औ

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

    मान लीजिए एक रेड-ब्लैक ट्री है, जहां किसी नोड की अधिकतम ऊंचाई न्यूनतम ऊंचाई से अधिकतम दोगुनी होती है। यदि हमारे पास एक बाइनरी सर्च ट्री है, तो हमें निम्न गुण की जांच करनी होगी: प्रत्येक नोड के संबंध में, सबसे लंबे लीफ-टू-नोड पथ की लंबाई, उस नोड से लीफ तक के सबसे छोटे पथ पर नोड्स की संख्या से दोगुनी