Kiểm tra xem Cây nhị phân nhất định có cân bằng chiều cao như Cây đỏ-đen trong Python hay không

Giả sử có một cây Đỏ-đen, ở đây chiều cao lớn nhất của một nút nhiều nhất là gấp đôi chiều cao nhỏ nhất. Nếu chúng ta có cây tìm kiếm nhị phân, chúng ta phải kiểm tra thuộc tính sau. Đối với mọi nút, chiều dài của đường đi từ nút đến nút dài nhất không quá gấp đôi các nút trên đường đi ngắn nhất từ ​​nút đến nút.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là True, vì điều này được cân bằng.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm giải quyết (). Điều này sẽ bắt nguồn gốc, max_height, min_height
• nếu gốc là null, thì
  • max_height:=0, min_height:=0
  • trả về True
• left_max:=0, left_min:=0
• right_max:=0, right_min:=0
• nếu giải quyết (root.left, left_max, left_min) giống False, thì
  • trả về Sai
• nếu giải quyết (root.right, right_max, right_min) giống với False, thì
  • trả về Sai
• max_height:=tối đa left_max và right_max + 1
• min_height:=tối thiểu left_min và right_min + 1
• nếu max_height <=2 * min_height, thì
  • trả về True
• trả về Sai
• Từ phương thức chính, hãy làm như sau -
• max_height:=0, min_height:=0
• trả về giải quyết (root, max_height, min_height)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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)

Đầu ra

True