Et vanlig BST kan degenerere til en koblet liste (O(n) operasjoner) hvis nøkler ankommer i sortert rekkefølge. Selvbalanserende BST-er — som AVL og rød-svarte trær — utfører automatisk rotasjoner etter innsettinger/slettinger for å holde høyden ~log n, noe som garanterer operasjoner.
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| AVL tre | Rød-svart tre | |
|---|---|---|
| Balanseringsstrenght | streng (høyde-balansert) | løsere |
| Oppslag | raskere (kortere) | litt langsommere |
| Innsetting/sletting | flere rotasjoner | færre rotasjoner |
| Best for | leseheavy arbeidsbelastninger | skriveheavy arbeidsbelastninger |
| Operasjon | Tid |
|---|---|
| søk | O(log n) |
| innsetting | O(log n) |
| sletting | O(log n) |
Begge opprettholder balanse via rotasjoner — lokale O(1) omstruktureringer som bevarer BST-ordeningen samtidig som høyden reduseres.
Balanserte trær støtter ordnede kart og sett i standardbiblioteker (f.eks. Java TreeMap, C++ std::map bruker rød-svarte trær), noe som gir sortert iterasjon pluss garanterte logaritmiske operasjoner.
De er svaret når du trenger et BSTs ordning og en hard ytelsesgaranti mot ondsinnet inndata.