जांचें कि क्या दिया गया बाइनरी ट्री पायथन में रेड-ब्लैक ट्री की तरह ऊंचाई संतुलित है

मान लीजिए कि एक लाल-काला पेड़ है, यहाँ एक नोड की सबसे बड़ी ऊँचाई न्यूनतम ऊँचाई से अधिक से अधिक दोगुनी है। यदि हमारे पास बाइनरी सर्च ट्री है, तो हमें निम्नलिखित संपत्ति की जांच करनी होगी। प्रत्येक नोड के संबंध में, सबसे लंबी पत्ती से नोड पथ की लंबाई नोड से पत्ती तक के सबसे छोटे पथ पर दोगुने से अधिक नहीं है।

तो, अगर इनपुट पसंद है

तो आउटपुट सही होगा, क्योंकि यह संतुलित है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन को हल करें() परिभाषित करें। यह जड़ लेगा, max_height, min_height
• यदि रूट रिक्त है, तो
  • अधिकतम_ऊंचाई:=0, न्यूनतम_ऊंचाई:=0
  • सही लौटें
• बाएं_अधिकतम:=0, बाएं_मिनट:=0
• right_max:=0, right_min:=0
• यदि हल (रूट.लेफ्ट, लेफ्ट_मैक्स, लेफ्ट_मिन) फाल्स के समान है, तो
  • झूठी वापसी
• यदि हल (root.right, right_max, right_min) False के समान है, तो
  • झूठी वापसी
• अधिकतम_ऊंचाई:=अधिकतम बाएं_अधिकतम और दाएं_अधिकतम + 1
• न्यूनतम_ऊंचाई :=न्यूनतम बाएं_मिनट और दाएं_मिनट + 1
• यदि max_height <=2 * min_height, तो
  • सही लौटें
• झूठी वापसी
• मुख्य विधि से निम्न कार्य करें -
• अधिकतम_ऊंचाई:=0, न्यूनतम_ऊंचाई:=0
• रिटर्न सॉल्व (रूट, max_height, min_height)

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

class TreeNode:
   def __init__(self, key):
      self.data = key
      self.left = None
      self.right = None
def solve(root, max_height, min_height) :
   if (root == None) :
      max_height = min_height = 0
      return True
   left_max=0
   left_min=0
   right_max, right_min=0,0
   if (solve(root.left, left_max, left_min) == False) :
      return False
   if (solve(root.right, right_max, right_min) == False) :
      return False
   max_height = max(left_max, right_max) + 1
   min_height = min(left_min, right_min) + 1
   if (max_height <= 2 * min_height) :
      return True
   return False
def is_tree_balanced(root) :
   max_height, min_height = 0,0
   return solve(root, max_height, min_height)
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(100)
root.right.left = TreeNode(50)
root.right.right = TreeNode(150)
root.right.left.left = TreeNode(40)
print(is_tree_balanced(root))

इनपुट

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(100)
root.right.left = TreeNode(50)
root.right.right = TreeNode(150)
root.right.left.left = TreeNode(40)

आउटपुट

True