주어진 Binary Tree가 Python의 Red-Black Tree처럼 높이 균형이 맞는지 확인하십시오.

Red-Black Tree가 있다고 가정합니다. 여기에서 노드의 가장 큰 높이는 최소 높이의 기껏해야 두 배입니다. 이진 탐색 트리가 있는 경우 다음 속성을 확인해야 합니다. 모든 노드와 관련하여 가장 긴 리프에서 노드까지의 경로 길이는 노드에서 리프까지의 최단 경로에서 노드의 두 배 이하입니다.

따라서 입력이 다음과 같으면

균형이 잡혀 있으므로 출력은 True가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• solve() 함수를 정의합니다. 이것은 root, max_height, min_height
를 취합니다.
• 루트가 null이면
  • 최대 높이:=0, 최소 높이:=0
  • 참 반환
• left_max :=0, left_min :=0
• right_max :=0, right_min :=0
• solve(root.left, left_max, left_min)가 False와 같으면
  • 거짓을 반환
• solve(root.right, right_max, right_min)가 False와 같으면
  • 거짓을 반환
• max_height :=left_max 및 right_max + 1의 최대값
• min_height :=left_min 및 right_min의 최소값 + 1
• max_height <=2 * min_height이면
  • 참 반환
• 거짓을 반환
• 메인 방법에서 다음을 수행하십시오 -
• 최대 높이:=0, 최소 높이:=0
• 해결(루트, 최대 높이, 최소 높이) 반환

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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