1 Introduction
2 Results
3 From Tree Covering to Hypersuccinct Trees
4 Universality for Fixed-Size Sources
4.1 Random BSTs
4.2 Weight-balanced trees
4.3 Other Sources
5 Hypersuccinct Range-Minimum Queries
5.1 Cartesian Trees
5.2 Random RMQ
5.3 RMQ with Runs
6 Conclusion
Appendix
A Related Work
A.1 Information Theory of Structure
A.2 Tree Compression
A.3 Succinct Trees
A.4 Compressed Tree Data Structures
A.5 Range-Minimum Queries
B Preliminaries
B.1 Trees
B.2 Succinct Data Structures
B.3 The Farzan-Munro Algorithm
I Binary Trees
C Hypersuccinct Binary Trees
C.1 Hypersuccinct Code
C.2 Tree Covering Data Structures
D Memoryless and Higher-Order Binary-Tree Sources
D.1 Universality of Memoryless and Higher-Order Sources
E Fixed-Size and Fixed-Height Binary Tree Sources
E.1 Fixed-Size Binary Tree Sources
E.2 Fixed-Height Binary-Tree Sources
E.3 Entropy of Fixed-Size and Fixed-Height Sources
E.4 Monotonic Tree Sources
E.5 Fringe-Dominated Tree Sources
E.6 Universality of Fixed-Size and Fixed-Height Sources
F Uniform-Subclass Sources
F.1 Universality for Uniform-Subclass Sources
G Range-Minimum Queries With Runs
G.1 Lower Bound
G.2 Hypersuccinct RMQ with Runs
II Ordinal Trees
H Hypersuccinct Ordinal Trees
H.1 Hypersuccinct Code
I Memoryless Ordinal Tree Sources
J Fixed-Size Ordinal Tree Sources
J.1 Monotonic Fixed-Size Sources
J.2 Fringe-Dominated Fixed-Size Ordinal Tree Sources
K Label-Shape Entropy
L Notation Index
L.1 Elementary Notation
L.2 Tree Notation
L.3 Tree Covering
L.4 Tree Sources
References
