Este un copac binar o stare structurală echilibrată?

Un arbore binar în sine nu este neapărat o stare structurală echilibrată. Un arbore binar echilibrat este unul în care înălțimile subarborilor stâng și drept pentru fiecare nod diferă cel mult cu 1. Această proprietate asigură accesul, inserția și ștergerea eficiente ale elementelor.

Dacă un arbore binar nu este echilibrat, în cel mai rău caz, se poate transforma într-o structură asemănătoare unei liste legate, ceea ce va deteriora performanța operațiilor.

Exemplu de verificare a echilibrului în Go (simplificat):

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
}

Prin urmare, un arbore binar poate fi atât echilibrat, cât și dezechilibrat, în funcție de structură și reguli de construcție.