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 $O(1)$ 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
$O({2}^{\alpha (n)})$ , improving upon the bound of ${2}^{\alpha (n{)}^{O(1)}}$ in
(Chalermsook et al., FOCS 2015). This is the best known bound obtained by any
online BSTs.
We settle the postorder traversal conjecture for Greedy.
The deque conjecture for Greedy holds up to a factor of $O(\alpha (n))$ ,
improving upon the bound ${2}^{O(\alpha (n))}$ in (Chalermsook, et al., WADS
2015).
The split conjecture holds for Greedy up to a factor of $O({2}^{\alpha (n)})$ .
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 $k$ -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).

PREPRINT

# 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

## Abstract

## Preprint

Comment: Accepted to SODA 2023

Subject: Computer Science - Data Structures and Algorithms