बाइनरी सर्च ट्री विभिन्न डेटा संरचनाओं में से एक है जो हमें डेटा को व्यवस्थित और सॉर्ट करने में मदद करती है। यह डेटा को पदानुक्रम में संग्रहीत करने का एक प्रभावी तरीका है और बहुत लचीला है।
इस लेख में, हम इसके गुणों और अनुप्रयोगों के साथ-साथ यह कैसे काम करता है, इस पर करीब से नज़र डालेंगे।
बाइनरी सर्च ट्री क्या है?
एक बाइनरी सर्च ट्री एक डेटा संरचना है जो नोड्स से बनी होती है - लिंक्ड लिस्ट के समान। दो प्रकार के नोड हो सकते हैं: एक माता-पिता और एक बच्चा। रूट नोड संरचना का शुरुआती बिंदु है जो दो चाइल्ड नोड्स में बंट जाता है, जिसे लेफ्ट नोड और राइट नोड कहा जाता है।
प्रत्येक नोड को केवल उसके माता-पिता द्वारा संदर्भित किया जा सकता है, और हम दिशा के आधार पर पेड़ के नोड्स को पार कर सकते हैं। बाइनरी सर्च ट्री में तीन मुख्य गुण होते हैं:
- बायां नोड अपने माता-पिता से छोटा है।
- दायां नोड अपने माता-पिता से बड़ा है।
- बाएँ और दाएँ सबट्री बाइनरी सर्च ट्री होने चाहिए।
एक संपूर्ण बाइनरी सर्च ट्री तब प्राप्त होता है जब सभी स्तर भर जाते हैं, और प्रत्येक नोड में एक बाएँ और दाएँ चाइल्ड नोड होता है।
सम्बंधित: पायथन के लिए डेटा विज्ञान पुस्तकालय प्रत्येक डेटा वैज्ञानिक को उपयोग करना चाहिए
एक बाइनरी सर्च ट्री के बुनियादी संचालन
अब आपको एक बेहतर विचार मिल गया है कि बाइनरी सर्च ट्री क्या है, हम नीचे इसके मूल संचालन को देख सकते हैं।
1. सर्च ऑपरेशन
खोज हमें पेड़ में मौजूद एक विशेष मूल्य का पता लगाने की अनुमति देती है। हम दो प्रकार की खोजों का उपयोग कर सकते हैं: चौड़ाई-प्रथम खोज (बीएफएस) और गहराई-प्रथम खोज (डीएफएस)। चौड़ाई-पहली खोज एक खोज एल्गोरिथ्म है जो रूट नोड से शुरू होता है और क्षैतिज रूप से, अगल-बगल, जब तक उद्देश्य नहीं मिल जाता है। इस खोज के दौरान प्रत्येक नोड का एक बार दौरा किया जाता है।
दूसरी ओर, गहराई-पहली खोज, पेड़ को लंबवत रूप से पार करती है—रूट नोड से शुरू होकर एक शाखा तक काम करती है। यदि उद्देश्य मिल जाता है, तो ऑपरेशन समाप्त हो जाता है। लेकिन यदि नहीं, तो यह अन्य नोड्स को खोजता है।
2. ऑपरेशन डालें
इंसर्ट ऑपरेशन उस स्थान को निर्धारित करने के लिए खोज ऑपरेशन का उपयोग करता है जहां नया नोड डाला जाना चाहिए। प्रक्रिया रूट नोड से शुरू होती है, और गंतव्य तक पहुंचने तक खोज शुरू होती है। सम्मिलन के साथ विचार करने के लिए तीन मामले हैं।
- केस 1: जब कोई नोड मौजूद नहीं है। डाला जाने वाला नोड रूट नोड बन जाएगा।
- केस 2: कोई संतान नहीं है। इस मामले में, नोड की तुलना रूट नोड से की जाएगी। अगर यह बड़ा है, तो यह सही बच्चा बन जाएगा; अन्यथा, यह वामपंथी संतान बन जाएगा।
- केस 3: जब जड़ और उसके बच्चे मौजूद हों। नए नोड की तुलना उसके पथ के प्रत्येक नोड से की जाएगी ताकि यह निर्धारित किया जा सके कि वह आगे किस नोड पर जाता है। यदि नोड रूट नोड से बड़ा है, तो यह दाएं उप-पेड़ को पार करेगा या फिर बाएं। इसी तरह, यह निर्धारित करने के लिए प्रत्येक स्तर पर तुलना की जाती है कि यह अपने गंतव्य पर पहुंचने तक दाएं या बाएं जाएगा।
3. ऑपरेशन हटाएं
डिलीट ऑपरेशन का उपयोग ट्री के भीतर एक विशेष नोड को हटाने के लिए किया जाता है। हटाना मुश्किल माना जाता है क्योंकि एक नोड को हटाने के बाद, पेड़ को उसी के अनुसार फिर से व्यवस्थित करना पड़ता है। विचार करने के लिए तीन मुख्य मामले हैं:
- केस 1: लीफ नोड को हटाना। एक पत्ता नोड बिना किसी बच्चे के नोड है। इसे हटाना सबसे आसान है क्योंकि यह किसी अन्य नोड को प्रभावित नहीं करता है; हम बस पेड़ को तब तक पार करते हैं जब तक हम उस तक नहीं पहुंच जाते और उसे हटा नहीं देते।
- केस 2: एक बच्चे के साथ एक नोड हटाना। माता-पिता को एक नोड के साथ हटाने से बच्चे को अपना स्थान मिल जाएगा, और बाद के सभी नोड्स एक स्तर ऊपर चले जाएंगे। उप-वृक्षों की संरचना में कोई परिवर्तन नहीं होगा।
- केस 3: दो बच्चों के साथ एक नोड हटाना। जब हमें दो बच्चों के साथ एक नोड को हटाना होता है, तो हमें पहले एक बाद वाला नोड ढूंढना होगा जो अपना स्थान ले सके। दो नोड हटाए गए नोड, इनऑर्डर उत्तराधिकारी या पूर्ववर्ती को प्रतिस्थापित कर सकते हैं। इनऑर्डर उत्तराधिकारी दाएं सबट्री का सबसे बाएं बच्चा है, और इनऑर्डर पूर्ववर्ती बाएं सबट्री का सबसे दाहिना बच्चा है। हम उत्तराधिकारी/पूर्ववर्ती की सामग्री को नोड में कॉपी करते हैं और इनऑर्डर उत्तराधिकारी/पूर्ववर्ती को हटा देते हैं।
सम्बंधित: जावास्क्रिप्ट ES6 कक्षाओं के साथ डेटा संरचनाएं कैसे बनाएं
बाइनरी सर्च ट्री को कैसे पार करें
ट्रैवर्सल वह प्रक्रिया है जिसके माध्यम से हम एक बाइनरी सर्च ट्री नेविगेट करते हैं। यह किसी विशिष्ट वस्तु का पता लगाने या पेड़ की रूपरेखा मुद्रित करने के लिए किया जाता है। हम हमेशा रूट नोड से शुरू करते हैं और अन्य नोड्स तक पहुंचने के लिए किनारों का अनुसरण करना पड़ता है। प्रत्येक नोड को एक उप-पेड़ माना जाना चाहिए, और प्रक्रिया तब तक दोहराई जाती है जब तक कि सभी नोड्स का दौरा न हो जाए।
- इन-ऑर्डर ट्रैवर्सल: ट्रैवर्सिंग इन-ऑर्डर आरोही क्रम में एक नक्शा तैयार करेगा। इस पद्धति के साथ, हम बाएं उपट्री से शुरू करते हैं और रूट और राइट सबट्री तक जारी रखते हैं।
- प्री-ऑर्डर ट्रैवर्सल: इस पद्धति में, पहले रूट नोड का दौरा किया जाता है, उसके बाद लेफ्ट सबट्री और राइट सबट्री का।
- पोस्ट-ऑर्डर ट्रैवर्सल: इस ट्रैवर्सल में अंतिम रूट नोड का दौरा करना शामिल है। हम बाएं सबट्री से शुरू करते हैं, फिर राइट सबट्री और फिर रूट नोड से।
वास्तविक दुनिया के अनुप्रयोग
तो, हम बाइनरी सर्च ट्री एल्गोरिदम का उपयोग कैसे करते हैं? जैसा कि अनुमान लगाया जा सकता है, वे खोज और छँटाई में बेहद कुशल हैं। बाइनरी ट्री की सबसे बड़ी ताकत उनकी संगठित संरचना है। यह हमें प्रति पास आधे से विश्लेषण करने के लिए आवश्यक डेटा की मात्रा में कटौती करके उल्लेखनीय गति से खोज करने की अनुमति देता है।
बाइनरी सर्च ट्री हमें एक व्यवस्थित रूप में गतिशील रूप से बदलते डेटासेट को कुशलतापूर्वक बनाए रखने की अनुमति देते हैं। उन अनुप्रयोगों के लिए जिनमें डेटा बार-बार डाला और हटाया जाता है, वे बहुत मददगार होते हैं। वीडियो गेम इंजन पेड़ों पर आधारित एक एल्गोरिथ्म का उपयोग करते हैं जिसे बाइनरी स्पेस पार्टीशन के रूप में जाना जाता है ताकि वस्तुओं को व्यवस्थित रूप से प्रस्तुत करने में मदद मिल सके। Microsoft Excel और अधिकांश स्प्रैडशीट सॉफ़्टवेयर अपने मूल डेटा संरचना के रूप में बाइनरी ट्री का उपयोग करते हैं।
आपको यह जानकर आश्चर्य हो सकता है कि मोर्स कोड डेटा को एन्कोड करने के लिए बाइनरी सर्च ट्री का उपयोग करता है। एक और प्रमुख कारण बाइनरी सर्च ट्री इतने उपयोगी हैं कि उनकी कई विविधताएं हैं। उनके लचीलेपन ने सभी प्रकार की समस्याओं को हल करने के लिए कई रूपों का निर्माण किया है। जब ठीक से उपयोग किया जाता है, तो बाइनरी सर्च ट्री एक महान संपत्ति है।
द्विआधारी खोज पेड़: बिल्कुल सही प्रारंभिक बिंदु
एक इंजीनियर की विशेषज्ञता का आकलन करने के मुख्य तरीकों में से एक उनके ज्ञान और डेटा संरचनाओं के अनुप्रयोग के माध्यम से है। डेटा संरचनाएं सहायक होती हैं और अधिक कुशल प्रणाली बनाने में मदद कर सकती हैं। बाइनरी सर्च ट्री शुरू करने वाले किसी भी डेवलपर के लिए डेटा संरचनाओं का एक बेहतरीन परिचय है।
जावास्क्रिप्ट सरणियों को समझना चाहते हैं, लेकिन उनके साथ पकड़ में नहीं आ सकते हैं? मार्गदर्शन के लिए हमारे जावास्क्रिप्ट सरणी उदाहरण देखें।
आगे पढ़िए
- प्रोग्रामिंग
- प्रोग्रामिंग
- प्रोग्रामिंग टूल्स
मैक्सवेल एक सॉफ्टवेयर डेवलपर हैं जो अपने खाली समय में एक लेखक के रूप में काम करते हैं। एक उत्साही तकनीकी उत्साही जो कृत्रिम बुद्धि की दुनिया में काम करना पसंद करता है। जब वह अपने काम में व्यस्त नहीं होता है, तो वह पढ़ना बंद कर देता है या वीडियो गेम खेल रहा होता है।
हमारे न्यूज़लेटर की सदस्यता लें
तकनीकी युक्तियों, समीक्षाओं, निःशुल्क ई-पुस्तकों और अनन्य सौदों के लिए हमारे न्यूज़लेटर से जुड़ें!
सब्सक्राइब करने के लिए यहां क्लिक करें
