Navadno BST se lahko izrodi v povezani seznam (O(n) operacije), če se ključi pojavljajo v sortiranem vrstnem redu. Samouravnotežena BST-ja — kot sta AVL in rdeče-črna drevesa — avtomatično rotirajo vozlišča po vstavljanju/brisanju, da ohranijo višino ~log n, kar zagotavlja 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 drevo | Rdeče-črno drevo | |
|---|---|---|
| Stroga uravnoteženost | stroga (višinsko uravnoteženo) | bolj ohlapna |
| Iskanja | hitrejša (krajša) | nekoliko počasnejša |
| Vstavljanje/brisanje | več rotacij | manj rotacij |
| Najboljše za | bralno intenzivne delovne obremenitve | pisalno intenzivne delovne obremenitve |
| Operacija | Čas |
|---|---|
| iskanje | O(log n) |
| vstavljanje | O(log n) |
| brisanje | O(log n) |
Obe ohranjavata uravnoteženost prek rotacij — lokalnih O(1) preureditev, ki ohranjajo urejanje BST-ja in zmanjšujejo višino.
Uravnotežena drevesa so osnova urejenih map in set-ov v standardnih knjižnicah (npr. Java TreeMap, C++ std::map uporabljajo rdeče-črna drevesa), kar omogoča sortirano iteracijo in garantirane logaritmske operacije.
So odgovor, ko potrebujete urejanje BST-ja in zagotovilo za zmogljivost pred sovražnostnimi vhodi.