Бинардык дарак балансталган түзүлүш абалыбы?

Өзүнчө экилик дарак өзүнчө милдеттүү түрдө тең салмактуу структура эмес. Тең салмактуу экилик дарак — бул ар бир түйүн үчүн сол жана оң алдындагы дарактардын бийиктиктери эң көп 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
}

Ошентип, экилик дарак анын түзүлүшүнө жана куруу эрежелерине жараша тең салмактуу же эмес болушу мүмкүн.