उदाहरण के साथ बाइनरी सर्च ट्री (BST)

बाइनरी सर्च ट्री क्या है?

बाइनरी सर्च ट्री एक उन्नत एल्गोरिथ्म है जिसका उपयोग नोड, इसकी बाईं और दाईं शाखाओं के विश्लेषण के लिए किया जाता है, जो एक पेड़ की संरचना में तैयार किए जाते हैं और मान लौटाते हैं। BST एक बुनियादी बाइनरी सर्च एल्गोरिथ्म की वास्तुकला पर आधारित है; इसलिए यह तेज लुकअप, इंसर्शन और नोड्स को हटाने में सक्षम बनाता है। यह कार्यक्रम को वास्तव में तेज और सटीक बनाता है।

इस डेटा संरचना ट्यूटोरियल में, आप सीखेंगे:

• बाइनरी सर्च ट्री क्या है?
• बाइनरी सर्च ट्री के गुण
• हमें बाइनरी सर्च ट्री की आवश्यकता क्यों है?
• बाइनरी पेड़ों के प्रकार
• बाइनरी सर्च ट्री कैसे काम करता है?
• महत्वपूर्ण शर्तें

बाइनरी सर्च ट्री के गुण

एक BST कई नोड्स से बना है और इसमें निम्नलिखित विशेषताएं हैं:

• पेड़ के नोड्स का प्रतिनिधित्व माता-पिता के बच्चे के रिश्ते में किया जाता है
• प्रत्येक माता-पिता के नोड में शून्य बच्चे के नोड्स या अधिकतम दो उप-नोड्स हो सकते हैं या बाईं और दाईं ओर उप-वर्ग हो सकते हैं।
• प्रत्येक उप-वृक्ष, जिसे एक द्विआधारी खोज वृक्ष के रूप में भी जाना जाता है, की उप-शाखाएँ स्वयं के दाईं और बाईं ओर होती हैं।
• सभी नोड्स कुंजी-मूल्य जोड़े के साथ जुड़े हुए हैं।
• बाईं उपरी पर मौजूद नोड्स की कुंजी उनके मूल नोड की कुंजी से छोटी होती है
• इसी प्रकार, द लेफ्ट सबट्री नोड्स की कुंजियों में उनके मूल नोड की कुंजियों की तुलना में कम मान होते हैं।

1. मुख्य नोड या मूल स्तर है 11. इसके तहत, अपने स्वयं के प्रमुख मूल्यों के साथ बाएं और दाएं नोड / शाखाएं हैं
2. सही उप-वृक्ष में मूल नोड से अधिक महत्वपूर्ण मूल्य हैं
3. बाएं उप-पेड़ में मूल नोड की तुलना में मान हैं

हमें बाइनरी सर्च ट्री की आवश्यकता क्यों है?

• बाइनरी सर्च ट्री को किसी भी वास्तविक दुनिया की समस्याओं का एक इष्टतम समाधान बनाने वाले दो प्रमुख कारक हैं स्पीड और एक्यूरेसी।
• इस तथ्य के कारण कि द्विआधारी खोज माता-पिता-बाल संबंधों के साथ एक शाखा-जैसे प्रारूप में है, एल्गोरिथ्म को पता है कि पेड़ के किस स्थान पर तत्वों को खोजना होगा। यह कुंजी-मूल्य की तुलना को घटाता है, जो प्रोग्राम को वांछित तत्व का पता लगाने के लिए बनाता है।
• इसके अतिरिक्त, मामले में मूल नोड की तुलना में अधिक या कम खोजे जाने वाले तत्व के लिए, नोड को यह पता होता है कि किस ट्री पक्ष की खोज करनी है। इसका कारण यह है, बायां उप-वृक्ष हमेशा मूल नोड से कम होता है, और सही उप-पेड़ में हमेशा मूल नोड के बराबर या उससे अधिक मूल्य होते हैं।
• BST का उपयोग आमतौर पर जटिल खोजों, मजबूत गेम लॉजिक्स, ऑटो-कम्प्लीट गतिविधियों और ग्राफिक्स को लागू करने के लिए किया जाता है।
• एल्गोरिथ्म कुशलता से खोज, सम्मिलित और हटाने जैसे कार्यों का समर्थन करता है।

बाइनरी पेड़ों के प्रकार

तीन प्रकार के द्विआधारी पेड़ हैं:

• पूर्ण बाइनरी ट्री: पेड़ों के सभी स्तर अंतिम स्तर के संभावित अपवादों से भरे हुए हैं। इसी तरह, सभी नोड्स भरे हुए हैं, बहुत दूर तक निर्देशित करते हैं।
• पूर्ण बाइनरी ट्री: सभी नोड्स में पत्ती को छोड़कर 2 बच्चे नोड होते हैं।
• बैलेंस्ड या परफेक्ट बाइनरी ट्री: ट्री में सभी नोड्स में दो बच्चे होते हैं। इसके अलावा, प्रत्येक उपनल का समान स्तर है।

बाइनरी सर्च ट्री कैसे काम करता है?

पेड़ में हमेशा जड़ नोड और आगे बच्चे नोड्स होते हैं, चाहे वह बाएं या दाएं पर हो। एल्गोरिथ्म सभी ऑपरेशनों को रूट और इसके आगे के बच्चे के नोड्स के साथ बाएं या दाएं उप-ट्री के अनुसार तुलना करके करता है।

तत्व को सम्मिलित करने, खोज करने या हटाने पर निर्भर करता है, तुलना के बाद, एल्गोरिथ्म आसानी से रूट नोड के बाएं या दाएं सबट्री को छोड़ सकता है।

BST मुख्य रूप से आपके उपयोग के लिए निम्नलिखित तीन प्रकार के संचालन प्रदान करता है:

• खोज: बाइनरी ट्री से तत्व को खोजता है
• सम्मिलित करें: बाइनरी ट्री में एक तत्व जोड़ता है
• हटाएं: एक बाइनरी ट्री से तत्व को हटाएं

प्रत्येक ऑपरेशन की अपनी संरचना और निष्पादन / विश्लेषण की विधि है, लेकिन सभी का सबसे जटिल है डिलीट ऑपरेशन।

सर्च ऑपरेशन

हमेशा रूट नोड पर पेड़ का विश्लेषण शुरू करें और फिर रूट नोड के दाएं या बाएं सबट्री या तो आगे बढ़ें, तत्व के आधार पर रूट की तुलना में कम या अधिक है।

1. खोजा जाने वाला तत्व 10 है
2. रूट नोड 12, 10 <12 के साथ तत्व की तुलना करें, इसलिए आप बाईं सबट्री पर जाते हैं। सही-उपशीर्षक का विश्लेषण करने की आवश्यकता नहीं है
3. अब नोड 7, 10> 7 के साथ 10 की तुलना करें, इसलिए दाईं-सबट्री पर जाएं
4. फिर अगले नोड के साथ 10 की तुलना करें, जो 9, 10> 9 है, सही उपशीर्षक बच्चे में देखें
5. नोड में मूल्य के साथ 10 मैच, 10 = 10, उपयोगकर्ता के लिए मूल्य वापस करते हैं।

ऑपरेशन डालें

यह बहुत ही सीधा फॉरवर्ड ऑपरेशन है। सबसे पहले, रूट नोड डाला जाता है, फिर अगले मान की तुलना रूट नोड के साथ की जाती है। यदि मान जड़ से अधिक है, तो इसे दाईं उप-सीमा में जोड़ा जाता है, और यदि यह जड़ से कम है, तो इसे बाएं उप-वर्ग में जोड़ा जाता है।

1. 6 तत्वों की एक सूची है, जिन्हें BST में बाएँ से दाएँ क्रम में सम्मिलित करने की आवश्यकता है
2. रूट नोड के रूप में 12 डालें और अगले मूल्यों 7 और 9 की तुलना दाएं और बाएं उपशीर्षक में डालें
3. शेष नोड्स 19, 5, और 10 की तुलना रूट नोड 12 से करें और उनके अनुसार रखें। 19> 12 इसे 12, 5 <12 & 5 <7 के दाएं बच्चे के रूप में रखें, इसलिए इसे 7 के बाएं बच्चे के रूप में रखें।
   1. अब 10 की तुलना करें, 10 <12 है और 10 है> 7 और 10 है> 9, 10 को 9 के दाहिने उपशीर्षक के रूप में रखें।

ऑपरेशन हटाएं

अन्य सभी कार्यों के बीच डिलीट सबसे उन्नत और जटिल है। BST में विलोपन के लिए कई मामले हैं।

• केस 1- शून्य बच्चों वाला नोड: यह सबसे आसान स्थिति है, आपको बस उस नोड को हटाना होगा जिसमें आगे या दाएं या बाएं बच्चे नहीं हैं।
• केस 2 - एक बच्चे के साथ नोड: एक बार जब आप नोड को हटा देते हैं, तो बस उसके बच्चे के नोड को हटाए गए मान के मूल नोड के साथ कनेक्ट करें।
• केस 3 दो बच्चों के साथ नोड: यह सबसे कठिन स्थिति है, और यह निम्नलिखित दो नियमों पर काम करता है
  • 3 ए - ऑर्डर पूर्ववर्ती में: आपको दो बच्चों के साथ नोड को हटाने की आवश्यकता है और इसे हटाए गए नोड के बाईं ओर के सबसे बड़े मूल्य के साथ बदलें
  • 3 बी - ऑर्डर उत्तराधिकारी में: आपको दो बच्चों के साथ नोड को हटाने की आवश्यकता है और इसे हटाए गए नोड के दाईं-सबट्री पर सबसे बड़े मूल्य के साथ बदलें

1. यह विलोपन का पहला मामला है जिसमें आप एक ऐसे नोड को हटाते हैं जिसमें कोई संतान नहीं है। जैसा कि आप चित्र में देख सकते हैं कि 19, 10 और 5 के कोई संतान नहीं है। लेकिन हम 19 को हटा देंगे।
2. मान 19 हटाएं और नोड से लिंक हटा दें।
3. 19 के बिना BST की नई संरचना देखें

1. यह विलोपन का दूसरा मामला है जिसमें आप एक नोड को हटाते हैं जिसमें 1 बच्चा है, जैसा कि आप आरेख में देख सकते हैं कि 9 में एक बच्चा है।
2. नोड 9 को हटा दें और इसे अपने बच्चे के साथ बदलें 10 और 7 से 10 तक एक लिंक जोड़ें
3. 9 के बिना बीएसटी की नई संरचना देखें

1. यहां आप नोड 12 को हटा रहे हैं जिसमें दो बच्चे हैं
2. नोड का विलोपन पूर्ववर्ती शासन के क्रम के आधार पर होगा, जिसका अर्थ है कि 12 के बाएं सबट्री पर सबसे बड़ा तत्व इसे प्रतिस्थापित करेगा।
3. नोड 12 को हटाएं और इसे 10 के साथ बदलें क्योंकि यह बाईं सबट्री पर सबसे बड़ा मूल्य है
4. 12 को हटाने के बाद BST की नई संरचना देखें

1. 1 एक नोड 12 हटाएं जिसमें दो बच्चे हैं
2. 2 नोड का विलोपन ऑर्डर उत्तराधिकारी नियम के आधार पर होगा, जिसका अर्थ है कि 12 के दाईं ओर के सबसे बड़े तत्व को प्रतिस्थापित करेगा
3. 3 नोड 12 को हटाएं और इसे 19 के साथ बदलें क्योंकि यह सही सबट्री पर सबसे बड़ा मूल्य है
4. 4 12 को हटाने के बाद BST की नई संरचना देखें

महत्वपूर्ण शर्तें

• सम्मिलित करें - एक पेड़ में एक तत्व सम्मिलित करता है / एक पेड़ बनाता है।
• खोज - एक पेड़ में एक तत्व खोजता है।
• प्रीऑर्डर ट्रैवर्सल - एक ट्री को प्री-ऑर्डर तरीके से ट्रेस करता है।
• इन्वर्टर ट्रैवर्सल - एक ट्री को इन-ऑर्डर तरीके से ट्रावर्स करता है।
• पोस्टऑर्डर ट्रावर्सल - पोस्ट-ऑर्डर तरीके से एक पेड़ का पता लगाता है।

सारांश

• BST एक उन्नत स्तर का एल्गोरिदम है जो रूट नोड के साथ नोड मानों की तुलना के आधार पर विभिन्न ऑपरेशन करता है।
• माता-पिता-बच्चे पदानुक्रम में कोई भी बिंदु नोड का प्रतिनिधित्व करता है। कम से कम एक अभिभावक या रूट नोड हर समय मौजूद रहता है।
• एक बाएं सबट्री और राइट सबट्री हैं। बाईं सबट्री में ऐसे मान होते हैं जो रूट नोड से कम हैं। हालाँकि, सही सबट्री में एक मान होता है जो रूट नोड से अधिक होता है।
• प्रत्येक नोड में शून्य, एक या दो बच्चे हो सकते हैं।
• एक द्विआधारी खोज पेड़ खोज, डालने और हटाने जैसे प्राथमिक संचालन की सुविधा देता है।
• सबसे जटिल होने के कारण कई मामले हैं, उदाहरण के लिए, एक बच्चे के साथ एक नोड, एक बच्चे के साथ नोड और दो बच्चों के साथ नोड।
• एल्गोरिथ्म का उपयोग गेम, स्वतः पूर्ण डेटा और ग्राफिक्स जैसे वास्तविक दुनिया के समाधानों में किया जाता है।