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

Description

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

Parameters

$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

Space Complexity Graph

Time-Space Tradeoff