Ένα απλό BST μπορεί να κατακάσει σε μια συνδεδεμένη λίστα (λειτουργίες O(n)) εάν τα κλειδιά φτάσουν σε ταξινομημένη σειρά. Αυτο-ισορροπούμενα BST — όπως AVL και κόκκινα-μαύρα δέντρα — περιστρέφουν αυτόματα κόμβους μετά από εισαγωγές/διαγραφές για να διατηρήσουν το ύψος ~log n, εγγυώμενες λειτουργίες O(log n).
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| Δέντρο AVL | Κόκκινο-μαύρο δέντρο | |
|---|---|---|
| Αυστηρότητα ισορροπίας | αυστηρή (ισορροπημένη κατά ύψος) | πιο χαλαρή |
| Αναζητήσεις | ταχύτερα (πιο κοντά) | ελαφρώς πιο αργά |
| Εισαγωγή/διαγραφή | περισσότερες περιστροφές | λιγότερες περιστροφές |
| Καλύτερη για | φόρτια ανάγνωσης | φόρτια εγγραφής |
| Λειτουργία | Ώρα |
|---|---|
| αναζήτηση | O(log n) |
| εισαγωγή | O(log n) |
| διαγραφή | O(log n) |
Και τα δύο διατηρούν ισορροπία μέσω περιστροφών — τοπική αναδόμηση O(1) που διατηρεί τη σειρά BST και μειώνει το ύψος.
Τα ισορροπημένα δέντρα υποστηρίζουν ταξινομημένους χάρτες και σύνολα σε τυπικές βιβλιοθήκες (π.χ. Java TreeMap, C++ std::map χρησιμοποιούν κόκκινα-μαύρα δέντρα), παρέχοντας ταξινομημένη επανάληψη συν εγγυημένες λογαριθμικές λειτουργίες.
Είναι η απάντηση όταν χρειάζεστε την ταξινόμηση ενός BST και μια σκληρή εγγύηση απόδοσης ενάντια σε αντίδραση εισαγωγών.