Egy bináris fa egyensúlyban lévő szerkezeti állapot?

Az önmagában álló bináris fa nem feltétlenül kiegyensúlyozott szerkezet. Egy kiegyensúlyozott bináris fa olyan fa, amelyben minden csomópont bal és jobb alárendelt ágának magassága legfeljebb 1 különbségű. Ez a tulajdonság hatékony hozzáférést, beszúrást és törlést biztosít.

Ha a bináris fa nincs kiegyensúlyozva, akkor a legrosszabb esetben összekapcsolt listához hasonló struktúrává alakulhat, ami rontja a műveletek teljesítményét.

Egyszerűsített példa a kiegyensúlyozottság ellenőrzésére Go nyelven:

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
}

Ezért a bináris fa lehet kiegyensúlyozott vagy nem, a szerkezetétől és a felépítési szabályoktól függően.