Self-Balancing Trees Deletion

Description

Delete a given element from 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(logn)$	$O({1})$	Exact	Deterministic
Guibas, Sedgewick Red-Black Tree	1972	$O(logn)$	$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