Self-Balancing Trees Search: Difference between revisions

Revision as of 09:24, 10 April 2023

Search for a given element within a self-balancing tree.

$n$: size of tree

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({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

@@ Line 6: / Line 6: @@
 == Parameters ==
-n: size of tree
+$n$: size of tree
 == Table of Algorithms ==
@@ Line 16: / Line 16: @@
 |-
-| [[Hopcroft 2-3 Tree ( Self-Balancing Trees Search)|Hopcroft 2-3 Tree]] || 1970 || $O(logn)$ || $O({1})$ || Exact || Deterministic ||
+| [[Hopcroft 2-3 Tree ( Self-Balancing Trees Search)|Hopcroft 2-3 Tree]] || 1970 || $O(\log n)$ || $O({1})$ || Exact || Deterministic ||
 |-
-| [[Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Search)|Guibas, Sedgewick Red-Black Tree]] || 1972 || $O(logn)$ || $O({1})$ || Exact || Deterministic || [https://ieeexplore.ieee.org/document/4567957 Time]
+| [[Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Search)|Guibas, Sedgewick Red-Black Tree]] || 1972 || $O(\log n)$ || $O({1})$ || Exact || Deterministic || [https://ieeexplore.ieee.org/document/4567957 Time]
 |-
 | [[AVL Tree ( Self-Balancing Trees Search)|AVL Tree]] || 1962 || $O(logn)$ || $O({1})$ || Exact || Deterministic ||