A study on splay trees

We study the dynamic optimality conjecture, which predicts that splay trees are a form of universally efficient binary search tree, for any access sequence. We reduce this claim to a regular access bound, which seems plausible and might be easier to prove. This approach may be useful to establish dynamic optimality.

Authors

• Luís M.S. Russo

Keywords

• Data structures
• Binary search trees
• Splay trees
• Dynamic optimality
• Competitive analysis
• Amortized analysis