यह दिए गए बाइनरी ट्री में सबसे बड़े इंडिपेंडेंट सेट (LIS) का साइज़ ढूंढने का C++ प्रोग्राम है।
इंडिपेंडेंट सेट बाइनरी ट्री में नोड्स का एक सबसेट है जहां कोई भी दो नोड्स एक एज द्वारा कनेक्टेड नहीं हैं।
एल्गोरिदम
शुरुआत
डेटा d, लेफ्ट चाइल्ड पॉइंटर l और राइट चाइल्ड पॉइंटर r घोषित करने के लिए n स्ट्रक्चर बनाएं
दो इंटीजर्स के बीच अधिकतम लौटाने के लिए max() फ़ंक्शन कॉल करें
दिए गए बाइनरी ट्री में सबसे बड़े इंडिपेंडेंट सेट का साइज़ लौटाने के लिए LIS() फ़ंक्शन बनाएं
वर्तमान नोड को छोड़कर साइज़ निकालें
int size_excl = LIS(root->l) + LIS(root->r)
वर्तमान नोड को शामिल करके साइज़ निकालें
int size_incl = 1
if (root->l)
size_incl += LIS(root->l->l) + LIS(root->l->r)
if (root->right)
size_incl += LIS(root->r->l) + LIS(root->r->r)
दोनों साइज़ का अधिकतम लौटाएं
नया नोड बनाने के लिए फ़ंक्शन बनाएं
समाप्तिउदाहरण कोड
#include <iostream>
using namespace std;
struct n {
int d;
int lis;
struct n *l, *r;
};
int max(int x, int y) {
return (x > y) ? x : y;
}
int LIS(struct n *root) {
if (root == NULL)
return 0;
if (root->lis)
return root->lis;
if (root->l == NULL && root->r == NULL)
return (root->lis = 1);
int lis_excl = LIS(root->l) + LIS(root->r);
int lis_incl = 1;
if (root->l)
lis_incl += LIS(root->l->l) + LIS(root->l->r);
if (root->r)
lis_incl += LIS(root->r->l) + LIS(root->r->r);
root->lis = max(lis_incl, lis_excl);
return root->lis;
}
struct n* newnode(int d) {
struct n* t = (struct n *) malloc(sizeof(struct n));
t->d = d;
t->l = t->r = NULL;
t->lis = 0;
return t;
}
int main() {
struct n *root = newnode(30);
root->l = newnode(20);
root->l->l = newnode(10);
root->l->r = newnode(7);
root->l->r->l = newnode(9);
root->l->r->r = newnode(6);
root->r = newnode(50);
root->r->r = newnode(26);
cout << "सबसे बड़े इंडिपेंडेंट सेट का साइज़ है " << LIS(root);
return 0;
}आउटपुट
सबसे बड़े इंडिपेंडेंट सेट का साइज़ है 5ट्री संरचना
30
/ \
20 50
/ \ \
10 7 26
/ \
9 6
LIS नोड्स: {10, 9, 6, 26, 30} या {10, 9, 6, 26, 50} - साइज़ 5
समय जटिलता
- बिना मेमोइज़ेशन: O(2^n) - एक्सपोनेंशियल
- मेमोइज़ेशन के साथ (जैसा कोड में है): O(n) - प्रत्येक नोड एक बार प्रोसेस होता है
DP दृष्टिकोण
कोड lis फील्ड का उपयोग करके मेमोइज़ेशन करता है, जिससे प्रत्येक नोड के लिए LIS केवल एक बार गणना होता है।
