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