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.
IT pokalbių klausimų biblioteka su išsamiais atsakymais — nuo Junior iki Senior.
Paaukoti