Greedy BST (or simply Greedy) is an online self-adjusting binary search tree defined in the geometric view ([Lucas, 1988; Munro, 2000; Demaine, Harmon, Iacono, Kane, Patrascu, SODA 2009). Along with Splay trees (Sleator, Tarjan 1985), Greedy is considered the most promising candidate for being dynamically optimal, i.e., starting with any initial tree, their access costs on any sequence is conjectured to be within
factor of the offline optimal.
However, in the past four decades, the question has remained elusive even for
highly restricted input.
In this paper, we prove new bounds on the cost of Greedy in the ''pattern
avoidance'' regime. Our new results include:
The (preorder) traversal conjecture for Greedy holds up to a factor of
, improving upon the bound of in
(Chalermsook et al., FOCS 2015). This is the best known bound obtained by any
We settle the postorder traversal conjecture for Greedy.
The deque conjecture for Greedy holds up to a factor of ,
improving upon the bound in (Chalermsook, et al., WADS
The split conjecture holds for Greedy up to a factor of .
Key to all these results is to partition (based on the input structures) the
execution log of Greedy into several simpler-to-analyze subsets for which
classical forbidden submatrix bounds can be leveraged. Finally, we show the
applicability of this technique to handle a class of increasingly complex
pattern-avoiding input sequences, called -increasing sequences.
As a bonus, we discover a new class of permutation matrices whose extremal
bounds are polynomially bounded. This gives a partial progress on an open
question by Jacob Fox (2013).
Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition
Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Nidia Obscura Acosta, Akash Pareek, Sorrachai Yingchareonthawornchai
Submitted on 8 November 2022
Comment: Accepted to SODA 2023
Subject: Computer Science - Data Structures and Algorithms