Upper Bounds for Maximally Greedy Binary Search Trees

Details Upper Bounds for Maximally Greedy Binary Search Trees Upper Bounds for Maximally Greedy Binary Search Trees

2011-02-24

arxiv.org/abs/1102.4884v3

Computer Science

Data Structures and Algorithms

To appear, WADS 2011. rev 1: Fixed accidental upload of out-of-date Fig. 1; rev 2: Added figures and made updates based on rev

Scientific paper

At SODA 2009, Demaine et al. presented a novel connection between binary search trees (BSTs) and subsets of points on the plane. This connection was independently discovered by Derryberry et al. As part of their results, Demaine et al. considered GreedyFuture, an offline BST algorithm that greedily rearranges the search path to minimize the cost of future searches. They showed that GreedyFuture is actually an online algorithm in their geometric view, and that there is a way to turn GreedyFuture into an online BST algorithm with only a constant factor increase in total search cost. Demaine et al. conjectured this algorithm was dynamically optimal, but no upper bounds were given in their paper. We prove the first non-trivial upper bounds for the cost of search operations using GreedyFuture including giving an access lemma similar to that found in Sleator and Tarjan's classic paper on splay trees.

Affiliated with

Also associated with

No associations

Rating

Upper Bounds for Maximally Greedy Binary Search Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Upper Bounds for Maximally Greedy Binary Search Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Upper Bounds for Maximally Greedy Binary Search Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-86066