सत्यापित किया जा रहा एक पेड़ BST या नहीं अजगर

Question

मैं एक अभ्यास साक्षात्कार सवाल जो मुझसे कहता है कि अगर एक पेड़ एक संतुलित खोज पेड़ है या नहीं की पुष्टि करने और आपको सत्यापन विधि देना है कि क्या ... मैं

Class Node: 
def __init__(self, k, val): 
    self.key = k 
    self.value = val 
    self.left = None 
    self.right = None 

के रूप में वर्ग है पेड़ अधिकतम और के रूप में न्यूनतम मूल्यों के लिए

और अन्य समारोह परिभाषाओं

def tree_max(node): 
    maxleft = float('-inf') if not node.left else tree_max(node.left) 
    maxright = float('-inf') if not node.right else tree_max(node.right) 
    return max(node.value, maxleft, maxright) 

def tree_min(node): 
    minleft = float('-inf') if not node.right else tree_min(node.left) 
    minright = float('-inf') if not node.left else tree_min(node.right) 
    return min(node.value, minleft, minright) 

मेरे सत्यापन विधि के रूप में

def verify(node): 
    if tree_max(node.left) <= node.value and node.value <= tree_min(node.right): 
     if verify(node.left) and verify(node.right): 
      return True 
     else: 
      return False 
    else: 
     return False 

मेरी समस्या तब होती है जब मैं सत्यापन विधि को लागू करने का प्रयास करता हूं, जब भी मैं एक बीएसटी पेड़ बनाने की कोशिश करता हूं तब भी मुझे झूठा लगता है। मेरे कार्यान्वयन इस प्रकार है:

root= Node(10, "Hello") 
root.left = Node(15, "Fifteen") 
root.right= Node(30, "Thirty") 

print verify(root) 

root = Node(10, "Ten") 
root.right = Node(20, "Twenty") 
root.left = Node(5, "Five") 
root.left.right = Node(15, "Fifteen") 

print verify(root) 

दोनों मुझे झूठी दे रहे हैं ... वहाँ मेरा सत्यापन समारोह या मेरे न्यूनतम/अधिकतम समारोह के साथ एक समस्या है ... किसी भी मदद की सराहना की जाएगी।

Answer 1

मुझे आपके कोड में चार त्रुटियां दिखाई देती हैं।

1. सबसे पहले, शून्य बच्चों के लिए आपकी जांच tree_min में पीछे की ओर है। यही है, आप जांच कर रहे हैं कि node.rightnode.left तक पहुंचने से पहले मौजूद है, और इसके विपरीत।

2. दूसरा, tree.min एक पत्ता नोड पर बुलाए जाने पर नकारात्मक अनंतता देता है। आपको न्यूनतम गणना में सकारात्मक अनंतता का उपयोग करने की आवश्यकता है (नकारात्मक संस्करण अधिकतम संस्करण में सही है)।

3. तीसरा, आप verify के भीतर एक तर्क त्रुटि है, के रूप में यह बिना शर्त tree_min या tree_max कॉल करता है और उस पर ही बच्चे नोड्स है, भले ही उनमें से एक या दोनों None हैं। मैं सही काम करने के लिए कॉलर पर भरोसा करने के बजाय None पारित होने वाले सभी कार्यों को संभालने का सुझाव देता हूं। यह min और max कोड को थोड़ा सा सरल बनाता है!

4. आखिरकार, आप node.value पर अपनी तुलना कर रहे हैं, जो स्ट्रिंग आप प्रत्येक नोड दे रहे हैं। मुझे संदेह है कि आप इसके बजाय node.key का उपयोग करके तुलना करना चाहते हैं। एक स्ट्रैट (जैसे float("-inf")) की तुलना स्ट्रिंग (जैसे "ten") की तुलना में पाइथन 3 में एक त्रुटि है, और यहां तक ​​कि पाइथन 2 में भी जहां यह कानूनी है, शायद यह आपके काम की अपेक्षा नहीं करता है।

उन मुद्दों के साथ, मुझे वैध और अमान्य पेड़ बनाने पर अपेक्षित परिणाम मिलते हैं। हालांकि आपके दो उदाहरण दोनों अमान्य हैं, इसलिए यदि आप उनका परीक्षण करने के लिए उपयोग कर रहे थे, तो आपको हमेशा False परिणाम मिलेगा।

अंत में, कुछ मामूली शैली के मुद्दों (जो कि बग नहीं हैं, लेकिन फिर भी चीजें जिन्हें बेहतर किया जा सकता है)। पायथन जंजीर तुलना का समर्थन करता है, ताकि आप if कथन verify से tree_max(node.left) <= node.key <= tree_min(node.right) में सरल बना सकें। अतिरिक्त if कथन को घोंसला देने के बजाय आप and के साथ चेक को कनेक्ट करके कोड के उस भाग को और सरल बना सकते हैं।

यहाँ (, अजगर 3 का उपयोग हालांकि मुझे लगता है कि यह सब पीछे की ओर अजगर 2 के लिए संगत है) अपने कोड का एक संस्करण है कि मेरे लिए काम करता है:

class Node: 
    def __init__(self, k, val): 
     self.key = k 
     self.value = val 
     self.left = None 
     self.right = None 

def tree_max(node): 
    if not node: 
     return float("-inf") 
    maxleft = tree_max(node.left) 
    maxright = tree_max(node.right) 
    return max(node.key, maxleft, maxright) 

def tree_min(node): 
    if not node: 
     return float("inf") 
    minleft = tree_min(node.left) 
    minright = tree_min(node.right) 
    return min(node.key, minleft, minright) 

def verify(node): 
    if not node: 
     return True 
    if (tree_max(node.left) <= node.key <= tree_min(node.right) and 
     verify(node.left) and verify(node.right)): 
     return True 
    else: 
     return False 

root= Node(10, "Hello") 
root.left = Node(5, "Five") 
root.right= Node(30, "Thirty") 

print(verify(root)) # prints True, since this tree is valid 

root = Node(10, "Ten") 
root.right = Node(20, "Twenty") 
root.left = Node(5, "Five") 
root.left.right = Node(15, "Fifteen") 

print(verify(root)) # prints False, since 15 is to the left of 10 

Answer 2

आप आसानी से इस प्रकार यह कर सकते हैं ::

INT_MAX = 999999999 
INT_MIN = -999999999 

class Node : 
    def __init__(self,data): 
     self.data = data 
     self.left = None 
     self.right = None 

def isBST(node): 
    return (isBSTUtil(node, INT_MIN, INT_MAX)) 

def isBSTUtil(node, mini, maxi): 
    if node is None : 
     return True 
    if node.data < mini or node.data > maxi : 
     return False 
    return (isBSTUtil(node.left, mini ,node.data-1) and 
      isBSTUtil(node.right, node.data+1,maxi)) 

# Driver program to test above function 
root = Node(4) 
root.left = Node(2) 
root.right = Node(5) 
root.left.left = Node(1) 
root.left.right = Node(3) 

if (isBST(root)): 
    print "Is BST" 
else: 
    print "Not a BST"