Et almindeligt BST kan degenerere til en linklistet (O(n) operationer), hvis nøgler ankommer i sorteret rækkefølge. Selvbalancerende BST'er — som AVL og rød-sorte træer — roterer automatisk noder efter indsættelser/sletninger for at holde højden ~log n, hvilket garanterer O(log n) operationer.
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| AVL-træ | Rød-sort træ | |
|---|---|---|
| Balancestricthed | streng (højdebalanceret) | løsere |
| Opslag | hurtigere (kortere) | lidt langsommere |
| Indsættelse/sletning | flere rotationer | færre rotationer |
| Bedst til | læseintensive arbejdsbelastninger | skriveintensive arbejdsbelastninger |
| Operation | Tid |
|---|---|
| søg | O(log n) |
| indsæt | O(log n) |
| slet | O(log n) |
Begge opretholder balance gennem rotationer — lokale O(1) omstrukturering, der bevarer BST-ordning og reducerer højden.
Balancerede træer understøtter ordnede kort og sæt i standardbiblioteker (f.eks. Java TreeMap, C++ std::map bruger rød-sorte træer), hvilket giver sorteret iteration plus garanterede logaritmiske operationer.
De er svaret, når du har brug for et BST-s ordning og en hård ydeevnegaranti mod ondsindet input.