Ar dvejetainis medis yra subalansuotas struktūrinis būvis?

Savo pačiuose savyje dvejetainis medis nebūtinai yra subalansuota struktūra. Subalansuotas dvejetainis medis yra toks medis, kuriame kiekvieno mazgo kairiojo ir dešiniojo pošakų aukščiai skiriasi ne daugiau kaip 1. Šis bruožas užtikrina efektyvų prieigą, įterpimą ir ištrynimą elementų.

Jei dvejetainis medis nėra subalansuotas, blogiausiu atveju jis gali virsti į struktūrą, panašią į susietą sąrašą, kas pablogins operacijų našumą.

Pavyzdys, kaip patikrinti subalansuotumą Go kalba (supaprastintas):

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
}

Todėl, dvejetainis medis gali būti tiek subalansuotas, tiek nesubalansuotas, priklausomai nuo jo struktūros ir statybos taisyklių.