Un albero binario è uno stato strutturale equilibrato?

Un albero binario di per sé non è necessariamente uno stato strutturale bilanciato. Un albero binario bilanciato è un albero in cui le altezze dei sottoalberi sinistro e destro di ogni nodo differiscono di al massimo 1. Questa proprietà garantisce un accesso, inserimento e rimozione efficienti.

Se un albero binario non è bilanciato, nel peggiore dei casi può trasformarsi in una struttura simile a una lista collegata, il che peggiora le prestazioni delle operazioni.

Esempio di verifica del bilanciamento in Go (semplificato):

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
}

Pertanto, un albero binario può essere sia bilanciato che non, a seconda della sua struttura e delle regole di costruzione.