Un BST semplice può degenerare in una lista collegata (operazioni O(n)) se le chiavi arrivano in ordine ordinato. Gli alberi BST autoequilibranti — come AVL e alberi rosso-neri — eseguono automaticamente rotazioni sui nodi dopo inserimenti/eliminazioni per mantenere l'altezza ~, garantendo operazioni .
log nUnbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| Albero AVL | Albero rosso-nero | |
|---|---|---|
| Rigorosità dell'equilibrio | rigorosa (bilanciata in altezza) | più libera |
| Ricerche | più veloci (più corte) | leggermente più lente |
| Inserimento/eliminazione | più rotazioni | meno rotazioni |
| Ideale per | carichi di lettura intensiva | carichi di scrittura intensiva |
| Operazione | Tempo |
|---|---|
| ricerca | O(log n) |
| inserimento | O(log n) |
| eliminazione | O(log n) |
Entrambi mantengono l'equilibrio tramite rotazioni — ristrutturazioni locali O(1) che preservano l'ordinamento BST riducendo l'altezza.
Gli alberi bilanciati supportano mappe e insiemi ordinati nelle librerie standard (ad es. Java TreeMap, C++ std::map usano alberi rosso-neri), fornendo iterazione ordinata oltre a operazioni logaritmiche garantite.
Sono la soluzione quando è necessario l'ordinamento di un BST e una garanzia di prestazioni rigida contro input avversariali.