ბინარული ხე არის ბალანსირებული სტრუქტურული მდგომარეობა?

საკუთარი თავის ბინარული ხე არ არის აუცილებელი იყოს ბალანსირებული სტრუქტურა. ბალანსირებული ბინარული ხე არის ის, სადაც თითოეულ კვანძზე მარცხენა და მარჯვენა ქვედა ხეების სიმაღლე განსხვავდება არა უმეტეს 1-ის. ეს თვისება უზრუნველყოფს ეფექტიან წვდომას, ჩასმას და წაშლას.

თუ ბინარული ხე არ არის ბალანსირებული, ყველაზე უარესი შემთხვევა შეიძლება ის იყოს დაკავშირებული სია მსგავსი სტრუქტურაში, რაც ამცირებს ოპერაციების შესრულების სიჩქარეს.

მაგალითი ბალანსის შემოწმების Go-ში (სადაც არის გამარტივებული):

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    leftHeight := height(root.Left)
    rightHeight := height(root.Right)
    if abs(leftHeight - rightHeight) > 1 {
        return false
    }
    return isBalanced(root.Left) && isBalanced(root.Right)
}

func height(node *TreeNode) int {
    if node == nil {
        return 0
    }
    leftHeight := height(node.Left)
    rightHeight := height(node.Right)
    if leftHeight > rightHeight {
        return leftHeight + 1
    }
    return rightHeight + 1
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

ამიტომ, ბინარული ხე შეიძლება იყოს როგორც ბალანსირებული, ასევე არა, მისი სტრუქტურის და მშენებლობის წესების მიხედვით.