Bristol Algorithms Days 2016 Workshop on Efficient Algorithms and Lower Bounds

2 - 3 February 2016

 Overview  •  Programme  •  Registration  •  Local information

Self-Organizing Binary Search Trees: Recent Results

Kurt Mehlhorn

The dynamic optimality conjecture is perhaps 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 access sequence. The two main candidates for dynamic optimality in the literature 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 trivial for almost all sequences: the optimum access cost of most length-n sequences is Θ(n log n), achievable by any balanced BST.

Thus, the obvious missing step towards the conjecture is an understanding of the "easy" access sequences. Preorder sequences (the access sequence arises from a preorder traversal of a tree) can easily be served in linear time by an off-line algorithms. No online BST is known to serve them in linear time.

We prove (FOCS 2015) two different relaxations of the traversal conjecture for Greedy: (i) Greedy with an arbitrary initial tree is almost linear for preorder sequences. (ii) Greedy with a fixed initial tree is in fact linear. These statements are corollaries of our more general results that express the complexity of access sequences in terms of a pattern avoidance parameter k. Pattern avoidance is a well-established concept in combinatorics, and the classes of input sequences thus defined are rich, e.g. the k=3 case includes preorder sequences. For any sequence X with parameter k, our most general result shows that Greedy achieves the cost n 2α(n)O(k^2) where α is the inverse Ackermann function. Furthermore, a broad subclass of parameter-k sequences has a natural combinatorial interpretation as k- decomposable sequences. For this class of inputs, we obtain the n 2O(k2) bound for Greedy with a fixed initial tree. For k=3, these results imply (i) and (ii).

Splay trees satisfy the so-called access lemma. Many of the nice properties of splay trees follow from it. What makes self-adjusting binary search trees (BSTs) satisfy the access lemma? In our ESA 2015 paper, we give sufficient conditions for the access lemma to hold and give strong hints of their necessity.

Joint work with Parinya Chalermsook, Mayank Goswami, Lazlo Kosma, and Thatchaphol Saranurak (WADS 2015, ESA 2015, FOCS 2015)

Back