C++ প্রোগ্রাম: ইন্টারভাল ট্রি বাস্তবায়ন

ইন্টারভাল ট্রি হল একটি ক্রমবদ্ধ ট্রি ডেটা স্ট্রাকচার যা ইন্টারভাল ধারণ করে। এটি খুব দক্ষতার সাথে যেকোনো প্রদত্ত ইন্টারভাল বা পয়েন্টের সাথে ওভারল্যাপ করার সব ইন্টারভাল খুঁজে বের করতে সাহায্য করে। নিচে ইন্টারভাল ট্রি বাস্তবায়নের জন্য একটি C++ প্রোগ্রাম দেওয়া হলো।

শুরু
  insert() ফাংশন ট্রিতে নতুন নোড যোগ করতে ব্যবহৃত হয়:
    যদি ট্রি খালি হয়, নতুন নোডটি রুট হয়।
    রুটের ইন্টারভালের লো মান পান।
    যদি রুটের লো মান ছোট হয়, নতুন ইন্টারভাল বাম সাব-ট্রিতে যায়।
    অন্যথায়, নতুন নোড ডান সাব-ট্রিতে যায়।
    প্রয়োজনে, এই প্র조상ের max মান আপডেট করুন।
শেষ

শুরু
  intervalFind() ফাংশন একটি দেওয়া ইন্টারভাল ট্রিতে একটি প্রদত্ত ইন্টারভাল i অনুসন্ধান করে:
    যদি ট্রি খালি হয়, NULL রিটার্ন করুন।
    যদি প্রদত্ত ইন্টারভাল রুটের সাথে ওভারল্যাপ করে
      রুটের i রিটার্ন করুন।
    যদি রুটের বাম চাইল্ড থাকে এবং বাম চাইল্ডের max প্রদত্ত ইন্টারভালের চেয়ে বড় বা সমান হয়,
      তবে i বাম সাব-ট্রিতে একটি ইন্টারভালের সাথে ওভারল্যাপ করতে পারে।
    অন্যথায়, ইন্টারভাল শুধুমাত্র ডান সাব-ট্রিটের সাথে ওভারল্যাপ করতে পারে।
শেষ

#include 
using namespace std;

struct Interval { // ইন্টারাল ভেরিয়েবল ঘোষণা
    int l, h;
};

struct ITNod { // নোড ঘোষণা
    Interval *i;
    int max;
    ITNod *l, *r;
};

ITNod *newNode(Interval i) { // নতুন নোড তৈরি
    ITNod *t = new ITNod;
    t->i = new Interval(i);
    t->max = i.h;
    t->l = t->r = NULL;
    return t;
}

ITNod *insert(ITNod *r, Interval i) {
    if (r == NULL) return newNode(i);
    int l = r->i->l;
    if (i.l < l) r->l = insert(r->l, i);
    else r->r = insert(r->r, i);
    if (r->max < i.h) r->max = i.h;
    return r;
}

bool Overlap(Interval i1, Interval i2) { // দুটি ইন্টারাল ওভারল্যাপ করে কিনা চেক
    if (i1.l <= i2.h && i2.l <= i1.h) return true;
    return false;
}

Interval *intervalFind(ITNod *root, Interval i) {
    if (root == NULL) return NULL;
    if (Overlap(*(root->i), i)) return root->i;
    if (root->l != NULL && root->l->max >= i.l)
        return intervalFind(root->l, i);
    return intervalFind(root->r, i);
}

void inorder(ITNod *root) { // ইনঅর্ডার ট্রভার্সাল
    if (root == NULL) return;
    inorder(root->l);
    cout << "[" << root->i->l << ", " << root->i->h << "]" << " max = " << root->max << endl;
    inorder(root->r);
}

int main(int argc, char **argv) {
    Interval ints[] = { {5, 20}, {6, 7}, {3, 4}, {67, 26}, {3, 4} };
    int n = sizeof(ints) / sizeof(ints[0]);
    ITNod *root = NULL;
    for (int i = 0; i < n; i++) root = insert(root, ints[i]);
    cout << "In-order traversal of the constructed Interval Tree is\n";
    inorder(root);
    Interval x = {7, 6};
    cout << "\nSearching for interval [" << x.l << "," << x.h << "]";
    Interval *res = intervalFind(root, x);
    if (res == NULL) cout << "\nNo Overlapping Interval";
    else cout << "\nOverlaps with [" << res->l << ", " << res->h << "]";
}

In-order traversal of the constructed Interval Tree is
[3, 4] max = 4
[3, 4] max = 4
[5, 20] max = 26
[6, 7] max = 26
[67, 26] max = 26
Searching for interval [7,6]
Overlaps with [5, 20]