Self-Balancing Trees Insertion (Self-Balancing Trees Insertion)

Description

Insert a given element into a self-balancing tree.

Parameters

$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(b)$?	Exact	Deterministic
Scapegoat Tree	1989	$O(n)$	$O({1})$?	Exact	Deterministic	Time
Treap	1989	$O(n)$	$O({1})$?	Exact	Randomized	Time

Time Complexity Graph

Space Complexity Graph

Time-Space Tradeoff