Kas binaripuu on tasakaalustatud struktuuriline seisund?

Omaette binarõlg puudub tingimata tasakaalustatud struktuur. Tasakaalustatud binarõlg on selline, kus iga sõlme vasaku ja parema alampuu kõrguste erinevus ei ületa 1. See omadus tagab tõhusa juurdepääsu, sisestamise ja kustutamise.

Kui binarõlg ei ole tasakaalustatud, võib see kõige halvemal juhul muutuda struktuuriks, mis sarnaneb ühendatud nimekirjaga, mis halvendab operatsioonide jõudlust.

Näide tasakaalustatuse kontrollimisest Go keeles (lihtsustatud):

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
}

Seega, binarõlg võib olla nii tasakaalustatud kui ka tasakaalustamata, sõltuvalt selle struktuurist ja ehitamise reeglitest.