Self-Balancing Trees Search (Self-Balancing Trees Search)

From Algorithm Wiki
Revision as of 09:12, 28 April 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


Search for a given element within a self-balancing tree.


$n$: size of tree

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Hopcroft 2-3 Tree 1970 $O(\log n)$ $O({1})$ Exact Deterministic
Guibas, Sedgewick Red-Black Tree 1972 $O(\log n)$ $O({1})$ Exact Deterministic Time
AVL Tree 1962 $O(logn)$ $O({1})$ Exact Deterministic
Tarjan Splay Tree 1985 $O(n)$ $O({1})$ Exact Deterministic
Bayer, McCreight B-Tree 1970 $O(b*log(n)$/log(b))? $O({1})$ Exact Deterministic
Scapegoat Tree 1989 $O(nlogn)$ $O({1})$? Exact Deterministic Time
Treap 1989 $O(n)$ $O({1})$? Exact Randomized Time
Tango Tree 2004 $O((k+{1})$log(log(n))) Exact Deterministic Time

Time Complexity Graph

Self-Balancing Trees Search - Time.png