একটি বাইনারি সার্চ ট্রি (Binary Search Tree) হল একটি সোর্টেড বাইনারি ট্রি (sorted binary tree) যেখানে সব নোডে নিচের প্রোপার্টিগুলো থাকবে:
একটি নোডের রাইট সাব-ট্রি (right sub-tree) এর কী (key) এর প্যারেন্ট নোডের কী থেকে বড় হবে।
একটি নোডের লেফট সাব-ট্রি (left sub-tree) এর কী (key) এর প্যারেন্ট নোডের কী থেকে ছোট হবে।
সभी কী ভ্যালু ভিন্ন (distinct) হবে।
প্রতিটি নোডে দুইটির বেশি চাইল্ড (children) থাকবে না।
ক্লাস ডেসক্রিপশন (Class Descriptions):
শুরু class BST নিচের ফাংশনগুলো ডিক্লেয়ার করতে: search() = BST-এ একটি আইটেম সার্চ করতে। temp = root ইনিশিয়ালাইজ করুন; while(temp != NULL) depth বাড়ান if(temp→info == data) print data and depth else if(temp→info > data) temp = temp→l; else temp = temp→r; insert() = ট্রিতে আইটেম ইনসার্ট করতে: যদি ট্রি খালি থাকে, ডেটাকে রুট হিসেবে ইনসার্ট করুন। যদি ট্রি খালি না থাকে যদি data < root ডেটাকে লেফট চাইল্ড হিসেবে ইনসার্ট করুন। else ডেটাকে রাইট চাইল্ড হিসেবে ইনসার্ট করুন। del() = ট্রি থেকে একটি আইটেম ডিলিট করতে। casea() = del()-এর থেকে কল হয় যদি l = r = null। caseb() = del()-এর থেকে কল হয় যদি l != null, r = null। caseb() = del()-এর থেকে কল হয় যদি l = null, r != null। casec() = del()-এর থেকে কল হয় যদি l != null, r != null। inorder() নোড ট্রাভার্স করতে ইনঅর্ডার (inorder) হিসেবে: left – root – right. preorder() নোড ট্রাভার্স করতে প্রিঅর্ডার (preorder) হিসেবে: root – Left – right. postorder() নোড ট্রাভার্স করতে পোস্টঅর্ডার (postorder) হিসেবে: left – right – root শেষ
উদাহরণ কোড
# include <iostream> # include <cstdlib> using namespace std; struct nod//নোড ডিক্লেরেশন { int info; struct nod *l; struct nod *r; }*r; class BST { public://ফাংশন ডিক্লেরেশন void search(nod *, int); void find(int, nod **, nod **); void insert(nod *, nod *); void del(int); void casea(nod *,nod *); void caseb(nod *,nod *); void casec(nod *,nod *); void preorder(nod *); void inorder(nod *); void postorder(nod *); void show(nod *, int); BST() { r = NULL; } }; void BST::find(int i, nod **par, nod **loc)//আইটেমের পজিশন খুঁজে বের করুন { nod *ptr, *ptrsave; if (r == NULL) { *loc = NULL; *par = NULL; return; } if (i == r→info) { *loc = r; *par = NULL; return; } if (i < r→info) ptr = r→l; else ptr = r→r; ptrsave = r; while (ptr != NULL) { if (i == ptr→info) { *loc = ptr; *par = ptrsave; return; } ptrsave = ptr; if (i < ptr→info) ptr = ptr→l; else ptr = ptr→r; } *loc = NULL; *par = ptrsave; } void BST::search(nod *root, int data) //সার্চিং { int depth = 0; nod *temp = new nod; temp = root; while(temp != NULL) { depth++; if(temp→info == data) { cout<<"\nData found at depth: "<<depth<<endl; return; } else if(temp→info > data) temp = temp→l; else temp = temp→r; } cout<<"\n Data not found"<<endl; return; } void BST::insert(nod *tree, nod *newnode) { if (r == NULL) { r = new nod; r→info = newnode→info; r→l= NULL; r→r= NULL; cout<<"Root Node is Added"<<endl; return; } if (tree→info == newnode→info) { cout<<"Element already in the tree"<<endl; return; } if (tree→info > newnode→info) { if (tree→l != NULL) { insert(tree→l, newnode); } else { tree→l= newnode; (tree→l)→l = NULL; (tree→l)→r= NULL; cout<<"Node Added To Left"<<endl; return; } } else { if (tree→r != NULL) { insert(tree→r, newnode); } else { tree→r = newnode; (tree→r)→l= NULL; (tree→r)→r = NULL; cout<<"Node Added To Right"<<endl; return; } } } void BST::del(int i) { nod *par, *loc; if (r == NULL) { cout<<"Tree empty"<<endl; return; } find(i, &par, &loc); if (loc == NULL) { cout<<"Item not present in tree"<<endl; return; } if (loc→l == NULL && loc→r == NULL) { casea(par, loc); cout<<"item deleted"<<endl; } if (loc→l!= NULL && loc→r == NULL) { caseb(par, loc); cout<<"item deleted"<<endl; } if (loc→l== NULL && loc→r != NULL) { caseb(par, loc); cout<<"item deleted"<<endl; } if (loc→l != NULL && loc→r != NULL) { casec(par, loc); cout<<"item deleted"<<endl; } free(loc); } void BST::casea(nod *par, nod *loc ) { if (par == NULL) { r= NULL; } else { if (loc == par→l) par→l = NULL; else par→r = NULL; } } void BST::caseb(nod *par, nod *loc) { nod *child; if (loc→l!= NULL) child = loc→l; else child = loc→r; if (par == NULL) { r = child; } else { if (loc == par→l) par→l = child; else par→r = child; } } void BST::casec(nod *par, nod *loc) { nod *ptr, *ptrsave, *suc, *parsuc; ptrsave = loc; ptr = loc→r; while (ptr→l!= NULL) { ptrsave = ptr; ptr = ptr→l; } suc = ptr; parsuc = ptrsave; if (suc→l == NULL && suc→r == NULL) casea(parsuc, suc); else caseb(parsuc, suc); if (par == NULL) { r = suc; } else { if (loc == par→l) par→l = suc; else par→r= suc; } suc→l = loc→l; suc→r= loc→r; } void BST::preorder(nod *ptr) { if (r == NULL) { cout<<"Tree is empty"<<endl; return; } if (ptr != NULL) { cout<<ptr→info<<" "; preorder(ptr→l); preorder(ptr→r); } } void BST::inorder(nod *ptr)//ইনঅর্ডার ট্রাভার্সাল { if (r == NULL) { cout<<"Tree is empty"<<endl; return; } if (ptr != NULL) { inorder(ptr→l); cout<<ptr→info<<" "; inorder(ptr→r); } } void BST::postorder(nod *ptr)//পোস্টঅর্ডার ট্রাভার্সাল { if (r == NULL) { cout<<"Tree is empty"<<endl; return; } if (ptr != NULL) { postorder(ptr→l); postorder(ptr→r); cout<<ptr→info<<" "; } } void BST::show(nod *ptr, int level)//ট্রি প্রিন্ট করুন { int i; if (ptr != NULL) { show(ptr→r, level+1); cout<<endl; if (ptr == r) cout<<"Root→: "; else { for (i = 0;i < level;i++) cout<<" "; } cout<<ptr→info; show(ptr→l, level+1); } } int main() { int c, n,item; BST bst; nod *t; while (1) { cout<<"1.Insert Element "<<endl; cout<<"2.Delete Element "<<endl; cout<<"3.Search Element"<<endl; cout<<"4.Inorder Traversal"<<endl; cout<<"5.Preorder Traversal"<<endl; cout<<"6.Postorder Traversal"<<endl; cout<<"7.Display the tree"<<endl; cout<<"8.Quit"<<endl; cout<<"Enter your choice : "; cin>>c; switch(c) { case 1: t = new nod; cout<<"Enter the number to be inserted : "; cin>>t→info; bst.insert(r, t); break; case 2: if (r == NULL) { cout<<"Tree is empty, nothing to delete"<<endl; continue; } cout<<"Enter the number to be deleted : "; cin>>n; bst.del(n); break; case 3: cout<<"Search:"<<endl; cin>>item; bst.search(r,item); break; case 4: cout<<"Inorder Traversal of BST:"<<endl; bst.inorder(r); cout<<endl; break; case 5: cout<<"Preorder Traversal of BST:"<<endl; bst.preorder(r); cout<<endl; break; case 6: cout<<"Postorder Traversal of BST:"<<endl; bst.postorder(r); cout<<endl; break; case 7: cout<<"Display BST:"<<endl; bst.show(r,1); cout<<endl; break; case 8: exit(1); default: cout<<"Wrong choice"<<endl; } } }
আউটপুট
1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 1 Enter the number to be inserted : 6 Root Node is Added 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 1 Enter the number to be inserted : 7 Node Added To Right 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 1 Enter the number to be inserted : 5 Node Added To Left 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 1 Enter the number to be inserted : 4 Node Added To Left 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 3 Search: 7 Data found at depth: 2 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 3 Search: 1 Data not found 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 4 Inorder Traversal of BST: 4 5 6 7 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 5 Preorder Traversal of BST: 6 5 4 7 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 6 Postorder Traversal of BST: 4 5 7 6 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 7 Display BST: 7 Root→: 6 5 4 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 2 Enter the number to be deleted : 1 Item not present in tree 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 5 Preorder Traversal of BST: 6 5 4 7 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 2 Enter the number to be deleted : 5 item deleted 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 7 Display BST: 7 Root→: 6 4 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 8
