Action hook ‘save_post’ triggered when deleting posts

It’s probably easiest to just check the post status within your function.

Untested:

add_action( 'save_post', 'rewrite_post', 10, 2 );

function rewrite_post( $post_id ) {
    if ( 'trash' != get_post_status( $post_id ) ) {
        remove_action( 'save_post', 'rewrite_post' );
        $title = preg_replace( '/\_/', ' ', get_the_title( $post_id ) );
        $my_post = array( );
        $my_post['ID'] = $post_id;
        $my_post['post_title'] = $title;
        $my_post['post_status'] = 'publish';
        wp_update_post( $my_post );
        add_action( 'save_post', 'rewrite_post' );
    }
}