বাইনারি সার্চ ট্রি হল একটি বাইনারি ট্রি ডাটা স্ট্রাকচার যেখানে আমাদের 3টি বৈশিষ্ট্য রয়েছে -
-
নোডের বাইনারি সার্চ ট্রির বাম সাবট্রিতে নোডের কী থেকে কম কী সহ শুধুমাত্র নোড থাকে।
-
বাইনারি সার্চ ট্রি নোডের ডান সাবট্রিতে নোডের কী থেকে বড় কী সহ শুধুমাত্র নোড থাকে।
-
একটি সাবট্রির বাম এবং ডান প্রতিটি একটি বাইনারি অনুসন্ধান গাছ হতে হবে৷
অ্যালগরিদম
Begin function BSTUtill() If node is equals to NULL then Return 1. If data of node is less than minimum or greater than maximum data then Return 0. Traverse left and right sub-trees recursively. End.
উদাহরণ কোড
#include <iostream>
#include <cstdlib>
#include <climits>
using namespace std;
struct n {
int d;
n* l;
n* r;
};
int BSTUtil(n* node, int min, int max);
int isBST(n* node) {
return(BSTUtil(node, INT_MIN, INT_MAX));
}
int BSTUtil(struct n* node, int min, int max) {
if (node==NULL)
return 1;
if (node->d < min || node->d > max)
return 0;
return BSTUtil(node->l, min, node->d - 1) && BSTUtil(node->r, node->d + 1, max);
}
n* newN(int d) {
n* nod = new n;
nod->d = d;
nod->l = NULL;
nod->r = NULL;
return nod;
}
int main() {
n *root = newN(7);
root->l = newN(6);
root->r = newN(10);
root->l->l = newN(2);
root->l->r = newN(4);
if (isBST(root))
cout<<"The Given Binary Tree is a BST"<<endl;
else
cout<<"The Given Binary Tree is not a BST"<<endl;
n *root1 = newN(10);
root1->l = newN(6);
root1->r = newN(11);
root1->l->l = newN(2);
root1->l->r = newN(7);
if (isBST(root1))
cout<<"The Given Binary Tree is a BST"<<endl;
else
cout<<"The Given Binary Tree is not a BST"<<endl;
return 0;
} আউটপুট
The Given Binary Tree is not a BST The Given Binary Tree is a BST
