## 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- 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 α 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
2 bound for Greedy with a fixed initial
tree. For ^{O(k2)}k=3, these results imply (i) and (ii).
Splay trees satisfy the so-called Joint work with Parinya Chalermsook, Mayank Goswami, Lazlo Kosma, and Thatchaphol Saranurak (WADS 2015, ESA 2015, FOCS 2015) Back |