The Greedy Binary Search Tree is Non-trivially Competitive

2026/08/05 by Yuhao Guo, Seth Pettie, Daniel Skora +1
Computer Science · #cs.DS

paper · pdf

18 pages

arxiv created 2026/08/05 · arxiv updated 2026/08/06

Abstract

We prove that the \textsfGreedy binary search tree is 2^{O(√(loglog n))}-competitive. It is widely conjectured that \textsfGreedy is O(1)-competitive, but before this work it was not known to be f-competitive, for any non-trivial f(n)=o(log n). Our analysis differs from prior analyses of binary search trees. It takes what might be called a "scaling" approach, where the cost at a refined scale is related to the cost at a coarser scale, and Wilber's interleave lower bound.

Citations

• Splay trees are almost dynamically optimal
• The Group Access Bounds for Binary Search Trees
• Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition
• Settling the relationship between Wilber's bounds for dynamic optimality
• Splaying Preorders and Postorders
• Smooth heaps and a dual view of self-adjusting data structures
• Weighted dynamic finger in binary search trees
• Pattern-avoiding access in binary search trees
• Upper Bounds for Maximally Greedy Binary Search Trees
• Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture
• Dynamic Optimality — Almost
• Self-adjusting binary search trees