বাইনারি সার্চ ট্রি হলো একটি বাইনারি ট্রি ডেটা স্ট্রাকচার যাতে ৩টি প্রপার্টি থাকে
একটি নোডের বাম সাবট্রি শুধু সেটি নোডের কি থেকে ছোট কি-ওয়ালা নোড ধারণ করে।
একটি নোডের ডান সাবট্রি শুধু সেটি নোডের কি থেকে বড় কি-ওয়ালা নোড ধারণ করে।
একটি সাবট্রির বাম ও ডান ট্রি দুটোই অবশ্যই বাইনারি সার্চ ট্রি হতে হবে।
অ্যালগরিদম
শুরু function BSTUtill() যদি নোড NULL-এর সমান হয় তবে ১ রিটার্ন করে। যদি নোডের ডেটা মিনিমাম থেকে কম বা ম্যাক্সিমাম থেকে বেশি হয় তবে ০ রিটার্ন করুন। বাম ও ডান সাব-ট্রি রিকার্সিভলি ট্রাভার্স করুন। শেষ।
উদাহরণ কোড
#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 << "দেয়া ট্রি একটি BST" << endl; else cout << "দেয়া ট্রি একটি 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 << "দেয়া ট্রি একটি BST" << endl; else cout << "দেয়া ট্রি একটি BST নয়" << endl; return 0; }আউটপুট
দেয়া ট্রি একটি BST নয় দেয়া ট্রি একটি BST
