Vai binārais koks ir līdzsvarots strukturālais stāvoklis?

Pašā pašā laikā binārais koks nav obligāti līdzsvarota struktūra. Līdzsvarots binārais koks ir tāds, kur katra mezgla kreisās un labās apakškoku augstumi atšķiras ne vairāk kā par 1. Šī īpašība nodrošina efektīvu piekļuvi, ievietošanu un dzēšanu.

Ja binārais koks nav līdzsvarots, sliktākajā gadījumā tas var pārvērsties līdzīgā struktūrā kā sasaistīta saraksts, kas pasliktinās operāciju veiktspēju.

Piemērs, kā pārbaudīt līdzsvarotību Go valodā (vienkāršots):

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
}

Tādēļ binārais koks var būt gan līdzsvarots, gan neligzots, atkarībā no tā struktūras un būvniecības noteikumiem.