Un BST obișnuit poate degenera într-o listă legată (operații O(n)) dacă cheile sosesc în ordine sortată. BST-uri auto-echilibrate — cum ar fi AVL și arbori roșu-negru — execută automat rotații după inserări/ștergeri pentru a menține înălțimea ~log n, garantând operații .
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| Arbore AVL | Arbore roșu-negru | |
|---|---|---|
| Rigoare echilibru | strict (echilibrat după înălțime) | mai ușor |
| Căutări | mai rapid (mai scurt) | ușor mai lent |
| Inserare/ștergere | mai multe rotații | mai puține rotații |
| Cel mai bun pentru | sarcini intensive de citire | sarcini intensive de scriere |
| Operație | Timp |
|---|---|
| căutare | O(log n) |
| inserare | O(log n) |
| ștergere | O(log n) |
Ambele mențin echilibrul prin rotații — reestructurări locale O(1) care păstrează ordinea BST în timp ce reduc înălțimea.
Arbori echilibrați susțin hărți ordonate și seturi în bibliotecile standard (de ex. Java TreeMap, C++ std::map folosesc arbori roșu-negru), oferind iterație sortată plus operații logaritmice garantate.
Sunt răspunsul când ai nevoie atât de ordinea BST și o garanție de performanță dură împotriva intrării ostile.