Is een binaire boom een gebalanceerde structurele toestand?

Een binaire boom op zich hoeft niet noodzakelijk een gebalanceerde structuur te zijn. Een gebalanceerde binaire boom is een boom waarbij de hoogten van de linker- en rechteronderbomen van elke knoop niet meer dan 1 verschillen. Deze eigenschap zorgt voor efficiënte toegang, invoeging en verwijdering van elementen.

Als een binaire boom niet gebalanceerd is, kan deze in het ergste geval veranderen in een structuur die lijkt op een gekoppelde lijst, wat de prestaties van de operaties verslechtert.

Voorbeeld van het controleren van de balans in Go (vereenvoudigd):

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
}

Dus, een binaire boom kan zowel gebalanceerd als niet-gebalanceerd zijn, afhankelijk van de structuur en de bouwregels.