All Publications

Lazy Search Trees

Dec 2020 (Written: Sep 2020)

Bryce Sandlund and Sebastian Wild:

Foundations of Computer Science (FOCS) 2020
in S. Irani (ed.): FOCS 2020, IEEE, 2020, pp 704–715

| read herePDFDOI arXiv |

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).

Range of sortedness from priority queues over lazy search trees to binary search trees
Lazy search trees interpolate smoothly between priority queues and binary search trees.

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.