Upper bounds for maximally greedy binary search trees

DOI10.1007/978-3-642-22300-6_35zbMATH Open1342.68109arXiv1102.4884OpenAlexW2120181493MaRDI QIDQ5199261FDOQ5199261

Authors: Kyle Fox 

Publication date: 12 August 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1102.4884

Recommendations

• The geometry of binary search trees
• Greedy is an almost optimal deque
• Dynamic Optimality—Almost
• scientific article; zbMATH DE number 5237331
• Better analysis of binary search tree on decomposable sequences

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Searching and sorting (68P10)

Cited In (9)

• Self-adjusting binary search trees: what makes them tick?
• In pursuit of the dynamic optimality conjecture
• On the maximum cardinality search lower bound for treewidth
• Greedy is an almost optimal deque
• Maximal flow in branching trees and binary search trees
• The geometry of binary search trees
• A study on splay trees
• Better analysis of binary search tree on decomposable sequences
• Smooth heaps and a dual view of self-adjusting data structures

This page was built for publication: Upper bounds for maximally greedy binary search trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5199261)