binary search tree c
बाइनरी सर्च ट्री पर विस्तृत ट्यूटोरियल (BST) C ++ में संचालन, C ++ कार्यान्वयन, लाभ, और उदाहरण कार्यक्रम शामिल हैं:
एक बाइनरी सर्च ट्री या BST जिसे लोकप्रिय कहा जाता है, एक बाइनरी ट्री है जो निम्नलिखित शर्तों को पूरा करता है:
- नोड्स जो रूट नोड से कम होते हैं जिन्हें बीएसटी के बाएं बच्चों के रूप में रखा जाता है।
- नोड्स जो रूट नोड से अधिक हैं जिन्हें BST के सही बच्चों के रूप में रखा गया है।
- बाएं और दाएं उपप्रकार बाइनरी खोज पेड़ों को चालू करते हैं।
किसी विशेष अनुक्रम में चाबियों के आदेश देने की यह व्यवस्था प्रोग्रामर को खोज, डालने, हटाने, आदि जैसे कार्यों को और अधिक कुशलता से करने की सुविधा प्रदान करती है। यदि नोड्स का आदेश नहीं दिया जाता है, तो हमें ऑपरेशन परिणाम प्राप्त करने से पहले प्रत्येक नोड की तुलना करना पड़ सकता है।
=> पूर्ण सी ++ प्रशिक्षण श्रृंखला यहां देखें।
आप क्या सीखेंगे:
- बाइनरी सर्च ट्री सी ++
- बुनियादी संचालन
- बाइनरी सर्च ट्री इंप्लीमेंटेशन C ++
- BST के फायदे
- बीएसटी के अनुप्रयोग
- निष्कर्ष
- अनुशंसित पाठ
बाइनरी सर्च ट्री सी ++
एक नमूना बीएसटी नीचे दिखाया गया है।
बाइनरी सर्च ट्रीज़ को नोड्स के इस विशिष्ट ऑर्डर के कारण 'ऑर्डर किए गए बाइनरी ट्रीज़' के रूप में भी जाना जाता है।
उपरोक्त BST से, हम देख सकते हैं कि बाएँ सबट्री में नोड्स हैं जो रूट से कम हैं यानी 45 हैं जबकि राइट सबट्री में नोड्स हैं जो 45 से अधिक हैं।
अब BST के कुछ बुनियादी कार्यों पर चर्चा करते हैं।
बुनियादी संचालन
# 1) डालें
सम्मिलित करें ऑपरेशन बाइनरी खोज ट्री में एक नया नोड जोड़ता है।
बाइनरी सर्च ट्री इंसर्ट ऑपरेशन के लिए एल्गोरिथ्म नीचे दिया गया है।
जावा में arrays.sort का उपयोग कैसे करें
Insert(data) Begin If node == null Return createNode(data) If(data >root->data) Node->right = insert(node->left,data) Else If(data data) Node->right = insert(node>right,data) Return node; endजैसा कि उपरोक्त एल्गोरिथम में दिखाया गया है, हमें यह सुनिश्चित करना होगा कि नोड को उचित स्थान पर रखा जाए ताकि हम BST आदेश का उल्लंघन न करें।
जैसा कि हम आरेख के उपरोक्त अनुक्रम में देखते हैं, हम सम्मिलित ऑपरेशन की एक श्रृंखला बनाते हैं। मूल नोड के साथ डाली जाने वाली कुंजी की तुलना करने के बाद, बाईं या दाईं उपप्रकार को कुंजी के लिए उपयुक्त स्थिति पर पत्ती नोड के रूप में डाला जाता है।
# 2) हटाएं
डिलीट ऑपरेशन BST से दी गई कुंजी से मेल खाने वाले नोड को हटा देता है। इस ऑपरेशन में, हमें हटाए जाने के बाद शेष नोड्स को भी बदलना होगा ताकि BST ऑर्डर का उल्लंघन न हो।
इसलिए हमें किस नोड को हटाना है इसके आधार पर, हमारे पास BST में विलोपन के लिए निम्नलिखित मामले हैं:
# 1) जब नोड एक लीफ नोड है
जब डिलीट किया जाने वाला नोड लीफ नोड होता है, तो हम सीधे नोड को हटा देते हैं।
# 2) जब नोड में केवल एक बच्चा होता है
जब हटाए जाने वाले नोड में केवल एक बच्चा होता है, तो हम बच्चे को नोड में कॉपी करते हैं और बच्चे को हटा देते हैं।
# 3) जब नोड के दो बच्चे हैं
यदि हटाए जाने वाले नोड में दो बच्चे हैं, तो हम नोड के लिए इनवर्टर उत्तराधिकारी ढूंढते हैं और फिर नोड के लिए इनवर्टर उत्तराधिकारी की प्रतिलिपि बनाते हैं। बाद में, हम इन्वर्टर उत्तराधिकारी को हटा देते हैं।
दो बच्चों के साथ नोड 6 को हटाने के लिए उपरोक्त पेड़ में, हम सबसे पहले उस नोड के लिए इन्वर्टर उत्तराधिकारी को हटाते हैं। हम सही सबट्री में न्यूनतम मूल्य पाकर इनवर्टर उत्तराधिकारी का पता लगाते हैं। उपरोक्त मामले में, न्यूनतम मूल्य सही उपप्रकार में 7 है। हम इसे हटाए जाने के लिए नोड पर कॉपी करते हैं और फिर इन्वर्टर उत्तराधिकारी को हटाते हैं।
# 3) खोजें
BST का खोज ऑपरेशन BST में 'कुंजी' के रूप में पहचाने गए किसी विशेष आइटम की खोज करता है। BST में किसी वस्तु को खोजने का लाभ यह है कि हमें पूरे पेड़ की खोज करने की आवश्यकता नहीं है। इसके बजाय BST में आदेश देने के कारण, हम बस मूल की कुंजी की तुलना करते हैं।
यदि कुंजी जड़ के समान है तो हम रूट को वापस करते हैं। यदि कुंजी रूट नहीं है, तो हम इसे रूट के साथ तुलना करके यह निर्धारित करते हैं कि क्या हमें बाएं या दाएं सबट्री की खोज करने की आवश्यकता है। एक बार जब हम सबट्री पाते हैं, तो हमें कुंजी की खोज करने की आवश्यकता होती है, और हम इसे फिर से किसी भी उपप्रकार में खोजते हैं।
निम्नलिखित BST में एक खोज अभियान के लिए एल्गोरिथ्म है।
Search(key) Begin If(root == null || root->data == key) Return root; If(root->key left,key) Else if (root->key >key ) Search(root->right,key); end 
यदि हम उपरोक्त पेड़ में मान 6 के साथ एक कुंजी को खोजना चाहते हैं, तो पहले हम कुंजी को रूट नोड के साथ तुलना करते हैं अर्थात् यदि (6 == 7) => नहीं तो (6)<7) =Yes; this means that we will omit the right subtree and search for the key in the left subtree.
अगला हम बाएं उप पेड़ से उतरते हैं। यदि (6 == 5) => नहीं।
यदि (6 नहीं, इसका मतलब 6> 5 है और हमें सही दिशा में आगे बढ़ना है।
अगर (6 == 6) => हाँ; चाबी मिल गई है।
# 4) ट्रैवर्सल्स
हम पहले से ही द्विआधारी पेड़ के लिए ट्रैवर्सल्स पर चर्चा कर चुके हैं। BST के मामले में भी, हम पेड़ को इनऑर्डर, प्रीऑर्डर या पोस्टऑर्डर क्रम से प्राप्त करने के लिए पार कर सकते हैं। वास्तव में, जब हम InST01 अनुक्रम में BST को पार करते हैं, तो हमें क्रमबद्ध अनुक्रम मिलता है।
हमने इसे नीचे चित्रण में दिखाया है।
उपरोक्त वृक्ष के लिए निम्न प्रकार हैं:
इनवर्टर ट्रैवर्सल (lnr): 3 5 6 7 8 9 10
प्रीऑर्डर ट्रैवर्सल (एलयूआरआर): 7 5 3 6 9 8 10
पोस्टऑर्डर ट्रैवरल (एलआरएन): 3 6 5 8 10 9 7
चित्रण
आइए नीचे दिए गए डेटा से एक बाइनरी सर्च ट्री का निर्माण करें।
45 30 60 65 70
आइए हम पहला तत्व रूट नोड के रूप में लेते हैं।
# 1) 45
सेल्सफोर्स डेवलपर साक्षात्कार प्रश्न और अनुभवी के लिए उत्तर
बाद के चरणों में, हम बाइनरी सर्च ट्री की परिभाषा के अनुसार डेटा को जगह देंगे अर्थात यदि डेटा मूल नोड से कम है, तो इसे बाएं बच्चे पर रखा जाएगा और यदि डेटा मूल नोड से अधिक है, तो यह सही बच्चा होगा।
इन चरणों को नीचे दिखाया गया है।
# 2) 30
# ३) ६०
# ४) ६५
# ५) )०
जब हम उपरोक्त BST पर इनवर्टर ट्रावेल करते हैं, जिसका हमने अभी निर्माण किया है, तो क्रम इस प्रकार है।
हम देख सकते हैं कि ट्रैवर्सल अनुक्रम में आरोही क्रम में तत्वों की व्यवस्था है।
बाइनरी सर्च ट्री इंप्लीमेंटेशन C ++
हमें C ++ कार्यान्वयन का उपयोग करके BST और उसके संचालन को प्रदर्शित करते हैं।
#include using namespace std; //declaration for new bst node struct bstnode { int data; struct bstnode *left, *right; }; // create a new BST node struct bstnode *newNode(int key) { struct bstnode *temp = new struct bstnode(); temp->data = key; temp->left = temp->right = NULL; return temp; } // perform inorder traversal of BST void inorder(struct bstnode *root) { if (root != NULL) { inorder(root->left); cout<data<<' '; inorder(root->right); } } /* insert a new node in BST with given key */ struct bstnode* insert(struct bstnode* node, int key) { //tree is empty;return a new node if (node == NULL) return newNode(key); //if tree is not empty find the proper place to insert new node if (key data) node->left = insert(node->left, key); else node->right = insert(node->right, key); //return the node pointer return node; } //returns the node with minimum value struct bstnode * minValueNode(struct bstnode* node) { struct bstnode* current = node; //search the leftmost tree while (current && current->left != NULL) current = current->left; return current; } //function to delete the node with given key and rearrange the root struct bstnode* deleteNode(struct bstnode* root, int key) { // empty tree if (root == NULL) return root; // search the tree and if key data) root->left = deleteNode(root->left, key); // if key > root, go for rightmost tree else if (key > root->data) root->right = deleteNode(root->right, key); // key is same as root else { // node with only one child or no child if (root->left == NULL) { struct bstnode *temp = root->right; free(root); return temp; } else if (root->right == NULL) { struct bstnode *temp = root->left; free(root); return temp; } // node with both children; get successor and then delete the node struct bstnode* temp = minValueNode(root->right); // Copy the inorder successor's content to this node root->data = temp->data; // Delete the inorder successor root->right = deleteNode(root->right, temp->data); } return root; } // main program int main() { /* Let us create following BST 40 / 30 60 65 70*/ struct bstnode *root = NULL; root = insert(root, 40); root = insert(root, 30); root = insert(root, 60); root = insert(root, 65); root = insert(root, 70); cout<<'Binary Search Tree created (Inorder traversal):'< आउटपुट:
बाइनरी सर्च ट्री बनाया (इनवर्टर ट्रैवर्सल):
30 40 60 65 70
नोड 40 हटाएं
संशोधित बाइनरी सर्च ट्री के लिए इनवर्टर ट्रावर्सल:
30 60 65 70
उपरोक्त कार्यक्रम में, हम इन-ऑर्डर ट्रैवर्सल अनुक्रम के लिए BST का उत्पादन करते हैं।
BST के फायदे
# 1) खोज बहुत कुशल है
हमारे पास एक विशिष्ट क्रम में BST के सभी नोड्स हैं, इसलिए किसी विशेष आइटम की खोज बहुत ही कुशल और तेज है। ऐसा इसलिए है क्योंकि हमें पूरे पेड़ की खोज करने और सभी नोड्स की तुलना करने की आवश्यकता नहीं है।
हमें बस रूट नोड की तुलना उस आइटम से करनी है जिसे हम खोज रहे हैं और फिर हम तय करते हैं कि हमें बाएं या दाएं सबट्री में खोजने की आवश्यकता है या नहीं।
# 2) कुशल काम जब ऐरे और लिंक्ड सूचियों की तुलना में
जब हम BST के मामले में किसी वस्तु की खोज करते हैं, तो हमें हर कदम पर बाएं या दाएं उप-भाग से आधे से छुटकारा मिलता है, जिससे खोज ऑपरेशन के प्रदर्शन में सुधार होता है। यह सरणियों या लिंक की गई सूचियों के विपरीत है जिसमें हमें किसी विशेष वस्तु को खोजने के लिए सभी वस्तुओं की क्रमिक रूप से तुलना करने की आवश्यकता होती है।
# 3) सम्मिलित करें और हटाएं तेज़
लिंक किए गए सूचियों और सरणियों जैसी अन्य डेटा संरचनाओं की तुलना में सम्मिलित करें और हटाएं संचालन भी तेज हैं।
बीएसटी के अनुप्रयोग
BST के कुछ प्रमुख अनुप्रयोग इस प्रकार हैं:
- BST का उपयोग डेटाबेस अनुप्रयोगों में बहुस्तरीय अनुक्रमण को लागू करने के लिए किया जाता है।
- BST का उपयोग डिक्शनरी को एक शब्दकोश की तरह लागू करने के लिए भी किया जाता है।
- BST का उपयोग विभिन्न कुशल खोज एल्गोरिदम को लागू करने के लिए किया जा सकता है।
- BST का उपयोग उन अनुप्रयोगों में भी किया जाता है जिन्हें ऑनलाइन स्टोर की तरह इनपुट के रूप में एक क्रमबद्ध सूची की आवश्यकता होती है।
- BST का उपयोग अभिव्यक्ति पेड़ों का उपयोग करके अभिव्यक्ति का मूल्यांकन करने के लिए भी किया जाता है।
निष्कर्ष
बाइनरी सर्च ट्री (BST) बाइनरी ट्री की विविधता है और सॉफ्टवेयर क्षेत्र में व्यापक रूप से उपयोग किया जाता है। उन्हें आदेशित बाइनरी ट्री भी कहा जाता है क्योंकि BST में प्रत्येक नोड को एक विशिष्ट आदेश के अनुसार रखा गया है।
BST के इनवर्टर ट्रैवर्सल हमें आरोही क्रम में वस्तुओं के क्रमबद्ध अनुक्रम प्रदान करते हैं। जब खोज के लिए BST का उपयोग किया जाता है, तो यह बहुत ही कुशल होता है और कुछ ही समय में किया जाता है। BSTs का उपयोग विभिन्न प्रकार के अनुप्रयोगों के लिए भी किया जाता है जैसे कि हफमैन की कोडिंग, डेटाबेस में बहुस्तरीय अनुक्रमण, आदि।
=> लोकप्रिय सी ++ प्रशिक्षण श्रृंखला के माध्यम से यहां पढ़ें।
अनुशंसित पाठ
- सी + + में बाइनरी ट्री डेटा संरचना
- AVL ट्री और ढेर डेटा संरचना C ++ में
- B ट्री और B + ट्री डेटा संरचना C ++ में
- C ++ में बेसिक इनपुट / आउटपुट ऑपरेशंस
- जावा में मूल I / O संचालन (इनपुट / आउटपुट स्ट्रीम)
- C ++ में पेड़: मूल शब्दावली, ट्रैवर्सल तकनीक और C ++ ट्री प्रकार
- फ़ाइल इनपुट आउटपुट ऑपरेशन C ++ में
- पॉइंटर्स और पॉइंटर ऑपरेशन C ++ में