ต้นไม้แบบทวิภาคที่สมดุล (Balanced Binary Tree) ใน Python

บทนำ

ในต้นไม้แบบทวิภาค (Binary Tree) แต่ละโหนดจะมีลูกได้สูงสุดสองโหนด คือ ลูกซ้าย (left child) และลูกขวา (right child) เราต้องการตรวจสอบว่าต้นไม้แบบทวิภาคที่กำหนดเป็นต้นไม้ที่ สมดุล (Balanced) หรือไม่ ต้นไม้แบบทวิภาคถือว่าสมดุลหากความแตกต่างของความสูงระหว่างต้นไม้รองซ้ายและต้นไม้รองขวาของทุกโหนดมีค่าไม่เกิน 1

ตัวอย่าง

Input-1:

Output:

True

คำอธิบาย:

ต้นไม้แบบทวิภาคที่กำหนดคือ [1,2,3, NULL, NULL, 6, 7] ความแตกต่างของความสูงระหว่างต้นไม้รองซ้ายและขวาคือ 1 จึงเป็นต้นไม้ที่สมดุลตามความสูง (height-balanced)

Input-2:

ต้นไม้แบบทวิภาคที่สมดุล (Balanced Binary Tree) ใน Python

Output:

False

คำอธิบาย:

ต้นไม้แบบทวิภาคที่กำหนดคือ [1,2,3,4, NULL, NULL, NULL, 5] ความแตกต่างของความสูงระหว่างต้นไม้รองซ้ายและขวามากกว่า 1 จึง ไม่ใช่ ต้นไม้ที่สมดุลตามความสูง

แนวทางแก้ปัญหา

วิธีแบบเรียกซ้ำ (Recursive) คือการหาความสูงของต้นไม้รองซ้ายและขวา จากนั้นตรวจสอบว่า |height(left) - height(right)| <= 1 และเรียกซ้ำตรวจสอบทุกโหนดในต้นไม้

รับค่าอินพุตของโหนดในต้นไม้แบบทวิภาค
กำหนดฟังก์ชันหาความสูงของต้นไม้
สร้างฟังก์ชัน Boolean เพื่อตรวจสอบแบบเรียกซ้ำว่าความแตกต่างของความสูงไม่เกิน 1 แล้วคืนค่า True
คืนค่าผลลัพธ์สุดท้าย

ตัวอย่างโค้ด Python

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = self.right = None

class Height:
    def __init__(self):
        self.height = 0

def isBalanced(root):
    lh = Height()
    rh = Height()
    if root is None:
        return True
    return (
        (abs(lh.height - rh.height) <= 1)
        and isBalanced(root.left)
        and isBalanced(root.right)
    )

# สร้างต้นไม้ตัวอย่าง
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = None
root.left.right = None
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

if isBalanced(root):
    print("Balanced")
else:
    print("Not Balanced")

ผลลัพธ์

Balanced

ต้นไม้แบบทวิภาค [1, 2, 3, NULL, NULL, 6, 7] มีความแตกต่างของความสูงระหว่างต้นไม้รองซ้ายและขวาเท่ากับ 1 จึงเป็นต้นไม้ที่สมดุลตามความสูง