বাইনারি সার্চ ট্রি (BST) একটি সর্টেড বাইনারি ট্রি যেখানে সব নোডের দুটি প্রপার্টি থাকে:
- রাইট সাব-ট্রির কী প্যারেন্ট নোডের কী থেকে বড়।
- লেফ্ট সাব-ট্রির কী প্যারেন্ট নোডের কী থেকে ছোট বা সমান।
- প্রতিটি নোডের দুইটির বেশি চাইল্ড থাকতে পারে না।
এটি বাইনারি সার্চ ট্রিতে ডিকশনারি অপারেশন (ইনসার্ট, সার্চ, ডিলিট) করার একটি C++ প্রোগ্রাম।
অ্যালগরিদম
ইনসার্টের জন্য:
Begin
insert(int k) ফাংশন ডিক্লেয়ার করুন
in = k mod max
p[in] = (n_type*) malloc(sizeof(n_type))
p[in]->d = k
if (r[in] == NULL) r[in] = p[in], r[in]->n = NULL, t[in] = p[in]
else t[in] = r[in], while (t[in]->n != NULL) t[in] = t[in]->n, t[in]->n = p[in]
End.সার্চের জন্য:
Begin
search(int k) ফাংশন ডিক্লেয়ার করুন
flag = 0, in = k mod max, t[in] = r[in]
while (t[in] != NULL)
if (t[in]->d == k) "Search key is found" প্রিন্ট করুন, flag = 1, break
else t[in] = t[in]->n
if (flag == 0) "search key not found" প্রিন্ট করুন
End.ডিলিটের জন্য:
Begin
delete_element(int k) ফাংশন ডিক্লেয়ার করুন
in = k mod max, t[in] = r[in]
while (t[in]->d != k && t[in] != NULL) p[in] = t[in], t[in] = t[in]->n
p[in]->n = t[in]->n
ডিলিট করা এলিমেন্ট প্রিন্ট করুন
t[in]->d = -1, t[in] = NULL, free(t[in])
Endউদাহরণ
#include <iostream>
#include <stdlib.h>
using namespace std;
#define max 20
typedef struct dictionary {
int d;
struct dictionary *n;
} n_type;
n_type *p[max], *r[max], *t[max];
class Dict {
public:
int in;
Dict();
void insert(int);
void search(int);
void delete_element(int);
};
// ... (সম্পূর্ণ কোড ইনপুটে আছে)
int main() {
// মেনু-চালিত ইন্টারফেসে ইনসার্ট, সার্চ, ডিলিট অপারেশন
}আউটপুট
1.Create 2.Search for a value 3.Delete a value Enter your choice:1 Enter the number of elements to be inserted:3 Enter the elements to be inserted:111 222 3333 Enter y to continue......y ... (ইন্টারঅ্যাক্টিভ আউটপুট)
