Оё дарахти дугона дар ҳолати баробарии сохторӣ аст?

Дархости худ, дархости биноӣ наметавонад структураи мувозинатнок бошад. Дархости биноӣ мувозинатнок он аст, ки баландии зерсохторҳои чап ва рост барои ҳар як нуқта на бештар аз 1 фарқ кунад. Ин хусусият дастрасӣ, ворид кардан ва хориҷ кардани унсурҳоро самаранок месозад.

Агар дархости биноӣ мувозинатнок набошад, дар ҳолати бадтарин метавонад ба структурае монанд ба рӯйхати пайвастшавӣ табдил ёбад, ки ин иҷрои амалҳоро камтар мекунад.

Масалан, санҷиши мувозинат дар Go (осонкардашуда):

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
}

Аз он, ки, дархости биноӣ метавонад ҳам мувозинатнок ва ҳам номувозинат бошад, вобаста ба сохтор ва қоидаҳои сохтани он.