Një BST e thjeshtë mund të degjenerojë në një listë të lidhur (operacione O(n)) nëse çelësat mbërrijnë në renditje të sortuar. BST-të e vetëbalancuara — si AVL dhe pemët e kuqe-zeza — rrotullojnë automatikisht nyjet pas futjeve/fshirjeve për të mbajtur lartësinë ~log n, duke garantuar operacionet .
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| Pema AVL | Pema e kuqe-zeza | |
|---|---|---|
| Rreptësia e balancimit | e rreptë (e balancuar në lartësi) | më e lirshme |
| Kërkimet | më të shpejta (më të shkurtra) | pak më të ngadalshme |
| Futje/fshirje | më shumë rrotullime | më pak rrotullime |
| Më e mirë për | ngarkesa të leximit intensiv | ngarkesa të shkrimit intensiv |
| Operacioni | Koha |
|---|---|
| kërkimi | O(log n) |
| futja | O(log n) |
| fshirja | O(log n) |
Te dyja mbajnë balancimin përmes rrotullimeve — ristrukturimeve lokale O(1) që ruajnë renditjen BST ndërsa zvogëlojnë lartësinë.
Pemët e balancuara mbështesin hartat dhe bashkësitë e renditura në biblioteka standarde (p.sh. Java TreeMap, C++ std::map përdorin pemë të kuqe-zeza), duke ofruar përsëritje të renditur plus operacione logaritmike të garantuara.
Ato janë përgjigja kur keni nevojë për renditjen e BST-së dhe një garanci të fortë të performancës kundër inputeve armiqësore.