এই প্রোগ্রামে আমাদের বাইনারি সার্চ ট্রিতে একটি সার্চ সিকোয়েন্সের অস্তিত্ব খুঁজে বের করতে হবে বাইনারি সার্চ বাস্তবায়ন করে। বাইনারি সার্চের বর্জ্য কেস সময় জটিলতা O(n) কিন্তু গড় কেসে O(log n)।
অ্যালগরিদম
শুরু দেওয়া অসর্টেড ডাটা অ্যারে থেকে একে একে ডাটা ইনসার্ট করে বাইনারি সার্চ ট্রি নির্মাণ করুন। BST-এ সার্চ করার ডাটা ইনপুট নিন। এখন রুট নোড থেকে শুরু করে ডাটাকে নোডের ডাটা অংশের সাথে তুলনা করুন। যদি ডাটা < temp->d, temp পয়েন্টারকে বাম চাইল্ডে সরান। যদি ডাটা > temp->d, temp পয়েন্টারকে ডান চাইল্ডে সরান। যদি ডাটা = temp->d, তবে যেখানে পাওয়া গেছে সেটি প্রিন্ট করুন এবং main-এ ফেরত যান। অন্যথায় আইটেম পাওয়া যায়নি প্রিন্ট করুন। শেষ
উদাহরণ কোড
#include <iostream>
using namespace std;
struct node {
int d;
node *left;
node *right;
};
node* CreateNode(int d) {
node *newnode = new node;
newnode->d = d;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
node* InsertIntoTree(node* root, int d) {
node *temp = CreateNode(d);
node *t = new node;
t = root;
if (root == NULL)
root = temp;
else {
while (t != NULL) {
if (t->d < d) {
if (t->right == NULL) {
t->right = temp;
break;
}
t = t->right;
} else if (t->d > d) {
if (t->left == NULL) {
t->left = temp;
break;
}
t = t->left;
}
}
}
return root;
}
void Search(node *root, int d) {
int depth = 0;
node *temp = new node;
temp = root;
while (temp != NULL) {
depth++;
if (temp->d == d) {
cout << "\nআইটেম " << depth << " গভীরতায় পাওয়া গেছে";
return;
} else if (temp->d > d)
temp = temp->left;
else
temp = temp->right;
}
cout << "\n আইটেম পাওয়া যায়নি";
return;
}
int main() {
char ch;
int n, i, a[10] = {93, 53, 45, 2, 7, 67, 32, 26, 71, 76};
node *root = new node;
root = NULL;
for (i = 0; i < 10; i++)
root = InsertIntoTree(root, a[i]);
up:
cout << "\nসার্চ করার উপাদান লিখুন: ";
cin >> n;
Search(root, n);
cout << "\n\n\tআরও সার্চ করতে চান...চয়েস লিখুন (y/n)? ";
cin >> ch;
if (ch == 'y' || ch == 'Y')
goto up;
return 0;
}
আউটপুট
সার্চ করার উপাদান লিখুন: 26 আইটেম 7 গভীরতায় পাওয়া গেছে আরও সার্চ করতে চান...চয়েস লিখুন (y/n)? সার্চ করার উপাদান লিখুন: 1 আইটেম পাওয়া যায়নি আরও সার্চ করতে চান...চয়েস লিখুন (y/n)?
