Un arbre binaire est-il un état structurel équilibré?

Un arbre binaire en soi n'est pas nécessairement une structure équilibrée. Un arbre binaire équilibré est un arbre où les hauteurs des sous-arbres gauche et droit de chaque nœud diffèrent d'au plus 1. Cette propriété garantit un accès, une insertion et une suppression efficaces.

Si un arbre binaire n'est pas équilibré, il peut, dans le pire des cas, se transformer en une structure semblable à une liste chaînée, ce qui dégrade la performance des opérations.

Exemple de vérification de l'équilibre en Go (de manière simplifiée) :

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
}

Ainsi, un arbre binaire peut être équilibré ou non, selon sa structure et ses règles de construction.