Lower Bounds for Accessing Binary Search Trees with Rotations
SIAM Journal on Computing1989Vol. 18(1), pp. 56–67
Citations Over TimeTop 12% of 1989 papers
Abstract
Two methods are given for obtaining lower bounds on the cost of accessing a sequence of nodes in a symmetrically ordered binary search tree, in a model where rotations can be done on the tree and the entire sequence is known before accessing begins (but the accesses must be done in the order given). For example, it can be proven that the bit-reversal permutation requires $\Theta (n\log n)$ time to access in this model. It is also shown that the expected cost of accessing random sequences in this model is the same as it is for the case where the tree is static.
Related Papers
- → Two Access Methods Using Compact Binary Trees(1987)39 cited
- → On the Generation of Random Binary Search Trees(1995)9 cited
- A non-recursive algorithm of constructing strict balance two binary search tree(2013)
- → Binary Trees and Binary Search Trees(2007)
- → Binary Trees and Binary Search Trees(2005)