স্বতন্ত্র সেট হল বাইনারি ট্রির সকল নোডের একটি সাবসেট যেখানে সেটের যেকোনো দুটি নোডের মধ্যে কোনো এজ (edge) নেই।
এখন একটি উপাদান সেট থেকে আমরা সর্বোচ্চ স্বতন্ত্র সেট খুঁজে বের করব। অর্থাৎ, যদি উপাদানগুলো বাইনারি ট্রি গঠন করে, তবে সবচেয়ে বড় সাবসেট যেখানে সেটের কোনো উপাদান পরস্পর সংযুক্ত নেই।
ইনপুট এবং আউটপুট
ইনপুট: একটি বাইনারি ট্রি।আউটপুট: সর্বোচ্চ স্বতন্ত্র সেটের আকার: ৫
অ্যালগরিদম
longSetSize(root)
এই অ্যালগরিদমে বাইনারি ট্রি গঠন করা হবে, প্রতিটি নোড ডেটা এবং setSize ধারণ করবে।
ইনপুট: বাইনারি ট্রির রুট নোড।
আউটপুট: সর্বোচ্চ সেটের আকার।
শুরু
যদি root = φ হয়, তবে
ফেরত দিন 0
যদি setSize(root) ≠ 0 হয়, তবে
ফেরত দিন setSize(root)
যদি root-এর কোনো চাইল্ড নেই, তবে
setSize(root) := 1
ফেরত দিন setSize(root)
setSizeEx := longSetSize(left(root)) + longSetSize(right(root)) // রুট বাদ দিয়ে
setSizeIn := 1
যদি বাম চাইল্ড থাকে, তবে
setSizeIn := setSizeIn + longSetSize(left(left(root))) + longSetSize(left(right(root)))
যদি ডান চাইল্ড থাকে, তবে
setSizeIn := setSizeIn + longSetSize(right(left(root))) + longSetSize(right(right(root)))
যদি setSizeIn > setSizeEx হয়, তবে
setSize(root) := setSizeIn
অন্যথায়
setSize(root) := setSizeEx
ফেরত দিন setSize(root)
শেষ
উদাহরণ (C++)
#include <iostream>
using namespace std;
struct node {
int data;
int setSize;
node *left, *right;
};
int longSetSize(node *root) {
if (root == NULL) return 0;
if (root->setSize != 0) return root->setSize;
if (root->left == NULL && root->right == NULL)
return (root->setSize = 1);
int setSizeEx = longSetSize(root->left) + longSetSize(root->right);
int setSizeIn = 1;
if (root->left)
setSizeIn += longSetSize(root->left->left) + longSetSize(root->left->right);
if (root->right)
setSizeIn += longSetSize(root->right->left) + longSetSize(root->right->right);
root->setSize = (setSizeIn > setSizeEx) ? setSizeIn : setSizeEx;
return root->setSize;
}
struct node* getNode(int data) {
node* newNode = new node;
newNode->data = data;
newNode->left = newNode->right = NULL;
newNode->setSize = 0;
return newNode;
}
int main() {
node *root = getNode(20);
root->left = getNode(8);
root->left->left = getNode(4);
root->left->right = getNode(12);
root->left->right->left = getNode(10);
root->left->right->right = getNode(14);
root->right = getNode(22);
root->right->right = getNode(25);
cout << "Size of the Largest Independent Set is: " << longSetSize(root);
}
আউটপুট
Size of the Largest Independent Set is: 5
