AVL Tree ( Self-Balancing Trees Search)

From Algorithm Wiki
Jump to navigation Jump to search

Time Complexity

$O(logn)$

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

1962

Reference