algorithm
जांचें कि कोई पेड़ BST है या नहीं
खोज…
यदि किसी दिए गए इनपुट ट्री में बाइनरी सर्च ट्री प्रॉपर्टी है या नहीं
उदाहरण के लिए
यदि इनपुट है:
आउटपुट गलत होना चाहिए:
बाएं उप-वृक्ष में 4 मूल मान से अधिक है (3)
यदि इनपुट है:
आउटपुट सही होना चाहिए
यह जांचने के लिए एल्गोरिथ्म है कि क्या दिया गया बाइनरी ट्री BST है
बाइनरी ट्री BST है यदि यह निम्नलिखित में से किसी एक को संतुष्ट करता है:
- यह खाली है
- इसका कोई उपप्रकार नहीं है
- पेड़ में प्रत्येक नोड x के लिए बाएं उप पेड़ में सभी कुंजी (यदि कोई हो) कुंजी (x) से कम होनी चाहिए और सही उप पेड़ में सभी कुंजी (यदि कोई हो) कुंजी (x) से अधिक होनी चाहिए।
तो एक सीधा पुनरावर्ती एल्गोरिदम होगा:
is_BST(root):
if root == NULL:
return true
// Check values in left subtree
if root->left != NULL:
max_key_in_left = find_max_key(root->left)
if max_key_in_left > root->key:
return false
// Check values in right subtree
if root->right != NULL:
min_key_in_right = find_min_key(root->right)
if min_key_in_right < root->key:
return false
return is_BST(root->left) && is_BST(root->right)
उपरोक्त पुनरावर्ती एल्गोरिथ्म सही लेकिन अक्षम है, क्योंकि यह प्रत्येक नोड म्यूटेंट समय का पता लगाता है।
प्रत्येक नोड की कई यात्राओं को कम करने के लिए एक और तरीका यह है कि हम जिस सबट्री में यात्रा कर रहे हैं उसमें कुंजियों के न्यूनतम और अधिकतम मूल्यों को याद रखें। किसी भी कुंजी का न्यूनतम संभव मान K_MIN और अधिकतम मान K_MAX होने K_MAX । जब हम पेड़ की जड़ से शुरू करते हैं, तो पेड़ में मूल्यों की सीमा [K_MIN,K_MAX] । रूट नोड की कुंजी x । फिर बाएँ सबट्री में मानों की श्रेणी [K_MIN,x) और दाएँ सबट्री में मानों की श्रेणी है (x,K_MAX] । हम इस विचार का उपयोग अधिक कुशल एल्गोरिथम विकसित करने के लिए करेंगे।
is_BST(root, min, max):
if root == NULL:
return true
// is the current node key out of range?
if root->key < min || root->key > max:
return false
// check if left and right subtree is BST
return is_BST(root->left,min,root->key-1) && is_BST(root->right,root->key+1,max)
इसे शुरू में कहा जाएगा:
is_BST(my_tree_root,KEY_MIN,KEY_MAX)
एक अन्य दृष्टिकोण बाइनरी ट्री के इनवर्टर ट्रैवर्सल को करना होगा। यदि इनवर्टर ट्रैवर्सल कुंजी के क्रमबद्ध क्रम का उत्पादन करता है तो दिए गए पेड़ एक BST है। यह जांचने के लिए कि क्या इनवर्टर अनुक्रम सॉर्ट किया गया है, पहले देखे गए नोड का मान याद रखें और वर्तमान नोड के खिलाफ तुलना करें।
