Self-Balancing Trees Deletion (Self-Balancing Trees Deletion)

From Algorithm Wiki
Revision as of 13:05, 15 February 2023 by Admin (talk | contribs)
Jump to navigation Jump to search

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

Error creating thumbnail: Unable to save thumbnail to destination

Space Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Pareto Frontier Improvements Graph

Error creating thumbnail: Unable to save thumbnail to destination