Entropy Trees and Range-Minimum Queries In Optimal Average-Case Space

Mar 2019 (Written: Feb 2019)

J. Ian Munro, and Sebastian Wild:

arXiv preprint 1903.02533

In this paper, we start the study of distribution-succinct data structures, i.e., data structures that have (asymptotically) optimal expected space usage (as opposed to only optimal worst case) for a certain data-structuring task.

We give such a distribution-succinct data structure for representing

binary search tree generated from random insertions (random BSTs) and
for answering range-minimum queries (RMQ).

An average-case space-optimal data structure for the RMQ problem was posed as open problem by Davoodi et al (2014).

Connection of RMQ and LCA queries — An example illustrating the close connection of range-maximum queries on an array and lowest common ancestor queries in binary trees.