Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Search)
Jump to navigation
Jump to search
Time Complexity
$O(\log n)$
Space Complexity
$O({1})$ words
(Need to keep track of constant amount of info during search (i.e. which node we're on and what direction to go))
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
1972