Ikki tarmoqli daraxt muvozanatli tuzilma holatimi?

O'z-o'zidan ikkilamchi daraxt majburan muvozanatli bo'lib, yoki bo'lmasligi mumkin. Muvozanatli ikkilamchi daraxt - bu har bir tugunning chap va o'ng bo'laklarining balandliklari 1 dan ortiq bo'lmagan farq bilan farqlanadigan daraxt. Bu xususiyat samarali kirish, qo'shish va o'chirishni ta'minlaydi.

Agar ikkilamchi daraxt muvozanatsiz bo'lsa, u eng yomon holatda bog'langan ro'yxatga o'xshash tuzilishga aylanishi mumkin, bu esa operatsiyalarning samaradorligini pasaytiradi.

Go tilida muvozanatni tekshirish misoli (soddalashtirilgan):

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
}

Shunday qilib, ikkilamchi daraxt uning tuzilishi va qurilish qoidalariga qarab muvozanatli yoki muvozanatsiz bo'lishi mumkin.