Obično BST može degeneriirati u povezanu listu (O(n) operacije) ako ključevi stignu u sortiranom redoslijedu. Samobalancirajuća BST-a — poput AVL i crvencrnih stabala — automatski rotiraju čvorove nakon umetanja/brisanja kako bi održali visinu ~log n, garantirajući operacije.
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| AVL stablo | Crvencrno stablo | |
|---|---|---|
| Strogost uravnoteženja | stroga (uravnotežena po visini) | fleksibilnija |
| Pretraga | brža (kraća) | malo sporija |
| Umetanje/brisanje | više rotacija | manje rotacija |
| Najbolje za | čitanjem intenzivno opterećenje | pisanjem intenzivno opterećenje |
| Operacija | Vrijeme |
|---|---|
| search | O(log n) |
| insert | O(log n) |
| delete | O(log n) |
Obje održavaju uravnoteženje kroz rotacije — lokalne O(1) restrukturalizacije koje čuvaju BST redoslijed dok smanjuju visinu.
Uravnotežena stabla podržavaju sortirane mape i skupove u standardnim bibliotekama (npr. Java TreeMap, C++ std::map koriste crvenocrna stabla), omogućavajući sortirane iteracije plus garantirane logaritamske operacije.
Oni su odgovor kada vam trebaju BST redoslijed i čvrsta garancija performansi protiv neprijateljskih ulaza.