बाइनरी सर्च ट्री (BST) एक विशेष प्रकार का बाइनरी ट्री है, जो दो प्रमुख गुणों का पालन करता है:
सभी बाएँ चाइल्ड नोड्स का मान उनके पेरेंट नोड से छोटा होता है
सभी दाएँ चाइल्ड नोड्स का मान उनके पेरेंट नोड से बड़ा होता है
इस तरह, हर नोड या तो किसी चाइल्ड नोड से खाली हो सकता है या बाईं तरफ एक छोटा नोड और दाईं तरफ एक बड़ा नोड रखता है।
8 नोड्स वाला एक बाइनरी सर्च ट्री
यह गुण बाइनरी ट्री में एलिमेंट्स खोजने के लिए बहुत उपयोगी होता है। यदि हम किसी मान x को ढूँढ रहे हैं, तो इस संरचना की वजह से हमें हमेशा पता रहता है कि उसे खोजने के लिए किस दिशा में आगे बढ़ना है। ऊपर दिए उदाहरण में, यदि हमें मान 3 वाला नोड ढूँढना हो, तो हम सबसे पहले रूट नोड (5) को जाँचते हैं। चूँकि 5, 3 से बड़ा है, हम बाईं ओर जाते हैं। इसके बाद हम मान 2 वाले नोड को देखते हैं; क्योंकि 2, 3 से छोटा है, हम दाईं ओर बढ़ते हैं। अब हम मान 4 वाले नोड पर आते हैं; चूँकि 4, 3 से बड़ा है, हम बाईं ओर जाते हैं। तब हमें मान 3 वाला नोड मिलता है, और क्योंकि 3, 3 के बराबर है, इसका मतलब हमने सही नोड ढूँढ लिया।
# मान लें कि गैर-मौजूद नोड्स None हैं, न कि 0
def search(node: Node | None, x: int):
""" यदि x ट्री में मौजूद है तो True लौटाएँ, वरना False """
if node is None: # यदि ट्री का अंत आ गया
return False # तो हमें मान x नहीं मिला
if x == node.value: # यदि x नोड के मान के बराबर है
return True # => हमने ट्री में x ढूँढ लिया
if x < node.value: # यदि x छोटा है => हमें बाईं ओर जाना होगा
return search(node.left) # बाएँ सब-ट्री में x ढूँढें
return search(node.right) # अन्यथा दाएँ सब-ट्री में कोशिश करें
इस प्रकार खोज करना तब बहुत प्रभावी हो सकता है जब ट्री की ऊँचाई ज़्यादा न हो। प्रत्येक चरण में हम या तो बाएँ या दाएँ सब-ट्री में जाते हैं, इसलिए सबसे बुरे हाल में खोज की कुल ऑपरेशन्स की संख्या लगभग ट्री की ऊँचाई के बराबर होती है।
चुनौती: जाँचें कि दिया गया ट्री BST है या नहीं
मान लीजिए कि आपके पास एक बाइनरी ट्री है, और आपको यह पता लगाना है कि क्या यह एक बाइनरी सर्च ट्री है।
इनपुट
इनपुट में स्पेस से अलग किए गए इंटीजर होते हैं, जो बाइनरी ट्री के नोड्स के मान दर्शाते हैं। इन मूल्यों की क्रमिक व्यवस्था हर बार बाएँ सब-ट्री से दाएँ सब-ट्री की ओर ट्रैवर्स करने से मिलती है। 0 का मान होना बताता है कि वह नोड मौजूद नहीं है। यह गारंटी दी जाती है कि इनपुट बाइनरी ट्री वैध है और सभी मान अद्वितीय हैं।
आउटपुट
यदि बाइनरी ट्री एक बाइनरी सर्च ट्री है तो प्रोग्राम को Yes प्रिंट करना चाहिए, अन्यथा No प्रिंट करना चाहिए।
Examples
Input
Output
1 2 3 8 5 0 0 0 0 5 8 0 0 0 0
No
5 2 7 1 4 0 0 3 0 0 0 6 8 0 0 0 0
Yes
Explanation
Example 1: हालाँकि सभी दाएँ चाइल्ड नोड्स अपने पेरेंट से बड़े हैं, लेकिन सभी बाएँ चाइल्ड नोड्स अपने पेरेंट से छोटे नहीं हैं।
Example 2: यह एक बाइनरी ट्री है क्योंकि बाएँ चाइल्ड नोड्स में पेरेंट से छोटे मान हैं और दाएँ चाइल्ड नोड्स में बड़े मान हैं।
.png?table=block&id=18a2c681-664d-811f-9fb0-eb124996dde6&cache=v2)
