Self-Balancing Trees Creation (Self-Balancing Trees Creation)

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


Create a self-balancing tree given a list of elements.


$n$: size of tree

Table of Algorithms

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

Time Complexity Graph

Self-Balancing Trees Creation - Time.png