Showing cs.DSShow all
3 papers · 1 filter
cs.DS2024
Greedy BST on Permutation Initial Tree
Akash Pareek
The Greedy binary search tree (BST) algorithm, like the Splay tree, is a prominent candidate for the \emph{dynamic optimality conjecture}. While Greedy satisfies many desirable pro…
cs.DS2023
The Group Access Bounds for Binary Search Trees
Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak +2
The access lemma (Sleator and Tarjan, JACM 1985) is a property of binary search trees that implies interesting consequences such as static optimality, static finger, and working se…
cs.DS2022
Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition
Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak +3
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…