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…