Lazy Search Trees

Watch Bryce’s talk about our paper here.

This paper marries the theory of efficient priority queues with the more powerful interface of binary search trees. Our lazy search trees can operate as a priority queue or a full sorted dictionary and – without changes to the data structure – performs close to optimal in both scenarios, (and indeed also in many intermediate ones).

The main technique is a new binary search tree variant that offers faster insertions – often $O(\log \log n)$ instead of $O(\log n)$ time / comparisons – when queries do not force us to sort (parts of) the stored elements.

Our actual performance statement is much more fine-grained and depends on the ranks of all queries executed on the lazy search tree. The performance matches a lower bound from multiple selection up to an additive $O(\log \log n)$ term per operation.

The data structure works on a pointer machine and is comparison based.

While the analysis requires a careful amortization argument, the data structure itself is easy to implement and has practical potential.