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

C++ प्रोग्राम इंटरवल ट्री लागू करने के लिए


एक इंटरवल ट्री एक ऑर्डर्ड ट्री डेटा संरचना है जो इंटरवल्स को होल्ड करती है। यह विशेष रूप से किसी दिए गए इंटरवल या पॉइंट के साथ ओवरलैप करने वाले सभी इंटरवल्स को कुशलतापूर्वक खोजने की अनुमति देती है।

एल्गोरिदम

  • insert(): ट्री में नए नोड्स डालने के लिए:
    • यदि ट्री खाली है, तो नया नोड रूट बन जाता है।
    • रूट पर इंटरवल का लो वैल्यू प्राप्त करें।
    • यदि रूट का लो वैल्यू छोटा है, तो नया इंटरवल बाएं सबट्री में जाता है।
    • अन्यथा, नया नोड दाएं सबट्री में जाता है।
    • यदि आवश्यक हो, तो इस पूर्वज के मैक्स वैल्यू को अपडेट करें।
  • intervalFind(): दिए गए इंटरवल ट्री में दिए गए इंटरवल i को खोजता है:
    • यदि ट्री खाली है तो NULL लौटाएं।
    • यदि दिया गया इंटरवल रूट के साथ ओवरलैप करता है, तो रूट->i लौटाएं।
    • यदि रूट का लेफ्ट चाइल्ड मौजूद है और लेफ्ट चाइल्ड का मैक्स दिए गए इंटरवल से बड़ा या बराबर है, तो इंटरवल बाएं सबट्री में ओवरलैप हो सकता है।
    • अन्यथा, इंटरवल केवल दाएं सबट्री में ओवरलैप हो सकता है।

C++ कार्यान्वयन

#include <iostream>
using namespace std;

struct Interval {
    int low, high;
};

struct ITNode {
    Interval *interval;
    int max;
    ITNode *left, *right;
};

ITNode* newNode(Interval i) {
    ITNode* temp = new ITNode;
    temp->interval = new Interval(i);
    temp->max = i.high;
    temp->left = temp->right = NULL;
    return temp;
}

ITNode* insert(ITNode* root, Interval i) {
    if (!root) return newNode(i);
    int l = root->interval->low;
    if (i.low < l)
        root->left = insert(root->left, i);
    else
        root->right = insert(root->right, i);
    if (root->max < i.high)
        root->max = i.high;
    return root;
}

bool overlaps(Interval i1, Interval i2) {
    return (i1.low <= i2.high && i2.low <= i1.high);
}

Interval* intervalSearch(ITNode* root, Interval i) {
    if (!root) return NULL;
    if (overlaps(*(root->interval), i))
        return root->interval;
    if (root->left && root->left->max >= i.low)
        return intervalSearch(root->left, i);
    return intervalSearch(root->right, i);
}

void inorder(ITNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << "[" << root->interval->low << ", " << root->interval->high << "]"
         << " max = " << root->max << endl;
    inorder(root->right);
}

int main() {
    Interval intervals[] = {{5, 20}, {6, 7}, {3, 4}, {10, 26}, {3, 4}};
    int n = sizeof(intervals)/sizeof(intervals[0]);
    ITNode* root = NULL;
    for (int i = 0; i < n; i++)
        root = insert(root, intervals[i]);
    
    cout << "In-order traversal of constructed Interval Tree:\n";
    inorder(root);
    
    Interval x = {7, 6};
    cout << "\nSearching for interval [" << x.low << "," << x.high << "]";
    Interval* res = intervalSearch(root, x);
    if (!res)
        cout << "\nNo Overlapping Interval";
    else
        cout << "\nOverlaps with [" << res->low << ", " << res->high << "]";
    return 0;
}

आउटपुट

In-order traversal of constructed Interval Tree:
[3, 4] max = 4
[3, 4] max = 4
[5, 20] max = 26
[6, 7] max = 26
[10, 26] max = 26

Searching for interval [7,6]
Overlaps with [5, 20]

जटिलता

  • इंसर्शन: O(log n) औसत, O(n) सबसे खराब स्थिति
  • ओवरलैप खोज: O(log n) औसत, O(n) सबसे खराब स्थिति
  • स्पेस: O(n)
  1. C++ में सीजर सिफर (Caesar Cipher) का कार्यान्वयन C++ में सीजर सिफर (Caesar Cipher) का कार्यान्वयन

    यह एक मोनो-अल्फाबेटिक सिफर है जिसमें प्लेनटेक्स्ट के प्रत्येक अक्षर को दूसरे अक्षर द्वारा प्रतिस्थापित किया जाता है ताकि सिफरटेक्स्ट बन सके। यह सब्स्टीट्यूशन सिफर योजना का सबसे सरल रूप है। इस क्रिप्टोसिस्टम को आमतौर पर शिफ्ट सिफर के रूप में संदर्भित किया जाता है। अवधारणा प्रत्येक अल्फाबेट को दूसरे

  1. C++ में AVL ट्री को लागू करना C++ में AVL ट्री को लागू करना

    AVL ट्री एक सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री है जहां सभी नोड्स के लिए बाएं और दाएं सबट्री की ऊंचाई का अंतर एक से अधिक नहीं हो सकता।ट्री रोटेशन एक ऑपरेशन है जो AVL ट्री पर एलिमेंट्स के क्रम में हस्तक्षेप किए बिना स्ट्रक्चर को बदलता है। यह ट्री में एक नोड को ऊपर ले जाता है और एक नोड को नीचे। इसका उपयो

  1. - C++ प्रोग्राम: टर्नरी ट्री कार्यान्वित करना

    एक टर्नरी ट्री, एक ट्री डेटा संरचना है जिसमें प्रत्येक नोड में अधिकतम तीन चाइल्ड नोड्स होते हैं, जिन्हें आमतौर पर लेफ्ट, मिड और राइट के रूप में दर्शाया जाता है। इस ट्री में, चाइल्ड वाले नोड्स पैरेंट नोड्स होते हैं, और चाइल्ड नोड्स में उनके पैरेंट्स के संदर्भ हो सकते हैं। यह टर्नरी ट्री को लागू करने