बाइनरी सर्च ट्री (BST) एक विशेष प्रकार का ट्री है जो निम्नलिखित नियमों का पालन करता है -
- बाएं चाइल्ड नोड का मान हमेशा पैरेंट नोट से कम होता है
- राइट चाइल्ड नोड का मान पैरेंट नोड से अधिक होता है।
- सभी नोड्स व्यक्तिगत रूप से एक बाइनरी सर्च ट्री बनाते हैं।
बाइनरी सर्च ट्री (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 में सम्मिलन ऑपरेशन
BST में सम्मिलन ऑपरेशन ट्री के लीफ नोड पर होता है। सम्मिलन के लिए हम नोड की तुलना रूट नोड से शुरू करेंगे और नोड की सही स्थिति ढूंढेंगे और फिर इसे रखेंगे। निम्नलिखित उदाहरण इसे आपके लिए और स्पष्ट कर देगा।
इस 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
