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

बाइनरी सर्च ट्री की विशेषताएँ

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

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

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

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

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

बाइनरी वृक्षों के प्रकार

बाइनरी वृक्ष तीन प्रकार के होते हैं:

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

इस बारे में अधिक जानें डेटा संरचना में बाइनरी ट्री अगर आपको रुचि हो तो।

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

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

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

बीएसटी मुख्य रूप से आपके उपयोग के लिए निम्नलिखित तीन प्रकार के ऑपरेशन प्रदान करता है:

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

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

खोजें Operaउत्पादन

विश्लेषण वृक्ष का आरंभ हमेशा मूल नोड से करें और फिर मूल नोड के दाएं या बाएं उपवृक्ष की ओर बढ़ें, यह इस बात पर निर्भर करता है कि स्थित किया जाने वाला तत्व मूल से छोटा है या बड़ा।

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

बीएसटी में खोज के लिए छद्म कोड

search(element, root)
     if !root
    	return -1
     if root.value == element
    	return 1
     if root.value < element
    	search(element, root.right)
      else
    	search(element, root.left)

सम्मिलित करें Operaउत्पादन

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

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

बीएसटी में नोड डालने के लिए छद्म कोड

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
    	y = x
    if x.value < element.value
        x = x.right
    else
        x = x.left
    if y.value < element
    	y.right = element
    else
    	y.left = element

मिटाना Operaमाहौल

BST से नोड को हटाने के लिए, कुछ मामले हैं, जैसे रूट को हटाना या लीफ नोड को हटाना। इसके अलावा, रूट को हटाने के बाद, हमें रूट नोड के बारे में सोचना होगा।

मान लीजिए कि हम एक लीफ नोड को हटाना चाहते हैं, तो हम उसे हटा सकते हैं, लेकिन अगर हम एक रूट को हटाना चाहते हैं, तो हमें रूट के मान को दूसरे नोड से बदलना होगा। आइए निम्नलिखित उदाहरण लेते हैं:

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

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

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

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

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

नोड को हटाने के लिए छद्म कोड

delete (value, root):
    Node x = root
    Node y = NULL
# searching the node
    while x:
    	y = x
    if x.value < value
        x = x.right
    else if x.value > value
        x = x.left
    else if value == x
        break
# if the node is not null, then replace it with successor
    if y.left or y.right:
    	newNode = GetInOrderSuccessor(y)
    	root.value = newNode.value
# After copying the value of successor to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

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

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

सारांश

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