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

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

इसलिए, यदि इनपुट इस तरह है:

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

समाधान दृष्टिकोण

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

• solve() फ़ंक्शन परिभाषित करें जो root, max_height, min_height लेता है।
• यदि root null है, तो:
  • max_height := 0, min_height := 0
  • True लौटाएं
• left_max := 0, left_min := 0, right_max := 0, right_min := 0 प्रारंभ करें।
• यदि solve(root.left, left_max, left_min) False लौटाता है, तो False लौटाएं।
• यदि solve(root.right, right_max, right_min) False लौटाता है, तो False लौटाएं।
• max_height := max(left_max, right_max) + 1 सेट करें।
• min_height := min(left_min, right_min) + 1 सेट करें।
• यदि max_height <= 2 * min_height है, तो True लौटाएं।
• अन्यथा False लौटाएं।
• मुख्य विधि से:
  • max_height := 0, min_height := 0 प्रारंभ करें।
  • solve(root, 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 is None:
        max_height = min_height = 0
        return True
    left_max = left_min = 0
    right_max = right_min = 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