Είναι ένα δυαδικό δέντρο μια ισορροπημένη δομική κατάσταση;

Ένα δικό του δυαδικό δέντρο δεν είναι απαραίτητα μια ισορροπημένη δομή. Ένα ισορροπημένο δυαδικό δέντρο είναι ένα δέντρο στο οποίο τα ύψη των αριστερών και δεξιών υποδέντρων κάθε κόμβου διαφέρουν το πολύ κατά 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
}

Επομένως, ένα δυαδικό δέντρο μπορεί να είναι τόσο ισορροπημένο όσο και μη, ανάλογα με τη δομή και τους κανόνες κατασκευής.