बाइनरी सर्च ट्री (BST) एक विशेष प्रकार का वृक्ष है जो निम्नलिखित नियमों का पालन करता है -
- बाएं चाइल्ड नोड का मान हमेशा पैरेंट नोट से कम होता है
- राइट चाइल्ड नोड का मान पैरेंट नोड से अधिक होता है।
- सभी नोड अलग-अलग बाइनरी सर्च ट्री बनाते हैं।
बाइनरी सर्च ट्री (BST) का उदाहरण -
खोज, न्यूनतम और अधिकतम खोजें जैसे कार्यों की जटिलता को कम करने के लिए बाइनरी सर्च ट्री बनाया जाता है।
बीएसटी में सर्च ऑपरेशन
बाइनरी सर्च ट्री में खोज करना,
हमें पेड़ में एक चाबी खोजने की जरूरत है। इसके लिए हम कुंजी की तुलना पेड़ के रूट नोड से करेंगे।
यदि कुंजी रूट नोड के बराबर है, तो कुंजी मिल जाती है।
यदि कुंजी का मान रूट नोड से अधिक है, तो सही सबट्री लें और कुंजी खोजें।
यदि कुंजी का मान रूट नोड से कम है, तो बाईं उपट्री लें और कुंजी खोजें।
उदाहरण
#include<stdio.h>
#include<stdlib.h>
struct node{
int key;
struct node *left, *right;
};
struct node *newNode(int item){
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void traversetree(struct node *root){
if (root != NULL){
traversetree(root->left);
printf("%d \t", root->key);
traversetree(root->right);
}
}
struct node* search(struct node* root, int key){
if (root == NULL || root->key == key)
return root;
if (root->key < key)
return search(root->right, key);
return search(root->left, key);
}
struct node* insert(struct node* node, int key){
if (node == NULL) return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
return node;
}
int main(){
struct node *root = NULL;
root = insert(root, 23);
insert(root, 15);
insert(root, 12);
insert(root, 17);
insert(root, 32);
insert(root, 29);
insert(root, 45);
printf("The tree is :\n");
traversetree(root);
printf("\nSearching for 12 in this tree ");
if(search(root , 12))
printf("\nelement found");
else
printf("\nelement not found");
return 0;
} आउटपुट
The tree is : 12 15 17 23 29 32 45 Searching for 12 in this tree element found
बीएसटी में इंसर्शन ऑपरेशन
एक बीएसटी में इंसर्शन ऑपरेशन पेड़ के लीफ नोड पर होता है इंसर्शन के लिए हम नोड की तुलना रूट नोड से शुरू करेंगे और नोड की सही स्थिति का पता लगाएंगे और फिर इसे रखेंगे। निम्नलिखित उदाहरण आपको इसे और स्पष्ट कर देगा।
इस BST में 12 सम्मिलित करना।
हम 12 की तुलना रूट नोड 12> 5 से करेंगे, यह सही सबट्री के अंतर्गत आता है।
12 की तुलना राइट चाइल्ड नोड 12> 8 से करें, यह राइट सब चाइल्ड के दाईं ओर है।
12 की तुलना राइट सबट्री 12>10 के राइट सब चाइल्ड से करें, इसकी स्थिति इस नोड के दाईं ओर है।
बनने वाला नया पेड़ होगा,
उदाहरण
#include<stdio.h>
#include<stdlib.h>
struct node{
int key;
struct node *left, *right;
};
struct node *newNode(int item){
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void traversetree(struct node *root){
if (root != NULL){
traversetree(root->left);
printf("%d \t", root->key);
traversetree(root->right);
}
}
struct node* insert(struct node* node, int key){
if (node == NULL) return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
return node;
}
int main(){
struct node *root = NULL;
root = insert(root, 23);
insert(root, 15);
insert(root, 12);
insert(root, 17);
insert(root, 32);
insert(root, 29);
printf("The tree is :\n");
traversetree(root);
printf("\nInseting 45 to the tree\n");
insert(root, 45);
printf("Tree after insertion is :\n");
traversetree(root);
return 0;
} आउटपुट
The tree is : 12 15 17 23 29 32 Inserting 45 to the tree Tree after insertion is : 12 15 17 23 29 32 45