ตรวจสอบว่า Binary Tree นั้นมีความสูงที่สมดุลเหมือน Red-Black Tree ใน Python . หรือไม่

สมมติว่ามีต้นไม้สีแดง-ดำ ที่นี่ความสูงที่ใหญ่ที่สุดของโหนดอยู่ที่ความสูงขั้นต่ำเป็นสองเท่า หากเรามีแผนผังการค้นหาแบบไบนารี เราต้องตรวจสอบคุณสมบัติต่อไปนี้ สำหรับโหนดทุกโหนด ความยาวของเส้นทางลีฟไปยังโหนดที่ยาวที่สุดมีไม่เกินสองเท่าของโหนดบนเส้นทางที่สั้นที่สุดจากโหนดหนึ่งไปอีกโหนดหนึ่ง

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น True เนื่องจากมีความสมดุล

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน Solve() สิ่งนี้จะทำการรูท, max_height, min_height
• ถ้ารูทเป็นโมฆะ
  • max_height :=0, min_height :=0
  • คืนค่า True
• left_max :=0, left_min :=0
• right_max :=0, right_min :=0
• ถ้าแก้ (root.left, left_max, left_min) เหมือนกับ False แล้ว
  • คืนค่าเท็จ
• ถ้าแก้(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 แล้ว
  • คืนค่า True
• คืนค่าเท็จ
• จากวิธีหลัก ให้ทำดังนี้ -
• max_height :=0, min_height :=0
• ผลตอบแทนการแก้(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