Self-Balancing Trees Creation: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 42: Line 42:
[[File:Self-Balancing Trees Creation - Space.png|1000px]]
[[File:Self-Balancing Trees Creation - Space.png|1000px]]


== Pareto Frontier Improvements Graph ==  
== Time-Space Tradeoff ==  


[[File:Self-Balancing Trees Creation - Pareto Frontier.png|1000px]]
[[File:Self-Balancing Trees Creation - Pareto Frontier.png|1000px]]

Revision as of 15:47, 15 February 2023

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(nlogn)$ $O(n)$ Exact Deterministic
Guibas, Sedgewick Red-Black Tree 1972 $O(nlogn)$ $O(n)$ Exact Deterministic Time
Hopcroft 2-3 Tree 1970 $O(nlogn)$ $O(n)$ Exact Deterministic
Tarjan Splay Tree 1985 $O(nlogn)$ $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

Self-Balancing Trees Creation - Time.png

Space Complexity Graph

Self-Balancing Trees Creation - Space.png

Time-Space Tradeoff

Self-Balancing Trees Creation - Pareto Frontier.png