特定の二分木がPythonの赤黒木と同じように高さのバランスが取れているかどうかを確認します

赤黒木があると仮定します。ここでは、ノードの最大の高さは最大で最小の高さの2倍です。二分探索木がある場合は、次のプロパティを確認する必要があります。すべてのノードに関して、リーフからノードへの最長パスの長さは、ノードからリーフへの最短パス上のノードの2倍以下です。

したがって、入力が次のような場合

バランスが取れているため、出力はTrueになります。

これを解決するには、次の手順に従います-

• 関数solve（）を定義します。これはルート、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：=left_maxとright_maxの最大値+1
• min_height：=left_minとright_minの最小値+1
• max_height <=2 * min_heightの場合、
  • Trueを返す
• Falseを返す
• メインの方法から次のようにします-
• max_height：=0、min_height：=0
• returnsolve（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 == 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