Paprastas BST gali susilpnėti į susietą sąrašą (O(n) operacijos), jei raktai atvyksta jų tvarka. Savaitraigė subalansavamosios BST — kaip AVL ir raudonai juodieji medžiai — automatiškai suktus mazgus po įterpimo/trynimo, kad aukštis liktų ~log n, garantuojant operacijas.
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| AVL medis | Raudonai juodas medis | |
|---|---|---|
| Balanso griežtumas | griežtas (aukščiu balansuotas) | žvalgiau |
| Paieška | greičiau (trumpiau) | šiek tiek lėčiau |
| Įterpimas/trynimas | daugiau suktų | mažiau suktų |
| Geriausiai skirta | skaitymo intensyviems darbams | rašymo intensyviems darbams |
| Operacija | Laikas |
|---|---|
| paieška | O(log n) |
| įterpimas | O(log n) |
| trynimas | O(log n) |
Abu išlaiko balansą per suktus — lokalūs O(1) pertvarkymai, kurie išsaugo BST tvarką sumažinant aukštį.
Subalansuoti medžiai pagrindžia sutvarkytas žemėlapius ir aibes standartinėse bibliotekose (pvz., Java TreeMap, C++ std::map naudoja raudonai juodus medžius), suteikiančius sutvarkytas iteracijas bei garantuotas logaritmines operacijas.
Tai atsakymas, kai jums reikalinga BST tvarka ir tvirtai garantuota veikla prieš priešiškus duomenis.