Self-Balancing Trees Search

Description

Search for a given element within 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({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

Space Complexity Graph

Time-Space Tradeoff