The dynamic optimality conjecture is the most fundamental open question about binary search trees (BST). It postulates the existence of an asymptotically optimal online BST, i.e., one that is constant factor competitive with any BST on any input sequence, even with one that knows the entire sequence in advance. The two main candidates for dynamic optimality are splay trees [Sleator and Tarjan, 1985] and GREEDY [Lucas, 1988; Munro, 2000; Demaine et al. 2009]. Despite BSTs being among the simplest data structures in computer science and despite extensive effort over the past three decades, the conjecture remains elusive. Dynamic optimality is achieved for almost all sequences, as the majority of them are hard and have optimum cost $\Theta(n \log n)$, achievable by any balanced BST. Thus the missing step towards the conjecture is understanding “easy” access sequences.
One prominent example is the traversal conjecture [Sleator and Tarjan, 1985] which states that preorder sequences are accessed in linear time by splay trees; no online BST was known to satisfy this conjecture until now.
In this talk I will survey the literature on dynamic optimality and present a proof of the traversal conjecture for GREEDY. I will also present a proof that Splay trees are not black magic, and end with some promising open problems. The talk will be accessible to anyone who knows what a binary tree is.
This talk is based on joint work (appearing in WADS, ESA and FOCS 2015, ISAAC 2018) with P. Charlemsook, K. Mehlhorn, L. Kozma and T. Saranurak.