###
Fully-Functional Succinct Trees

####
Kunihiko Sadakane and Gonzalo Navarro

We propose new succinct representations of ordinal trees,
which have been studied extensively. It is known that any *n*-node
static tree can be represented in *2n + o(n)* bits and various
operations on the tree can be supported in constant time under the
word-RAM model.
However existing data structures are not satisfactory in both theory
and practice because
(1) the lower-order term is *Omega(n log log n/ log n)* and
cannot be neglected,
(2) the hidden constant is also large, and
(3) the data structures are complicated and difficult to implement.
We propose a simple and flexible data structure, called the range min-max
tree, that reduces the large number of relevant tree operations considered in
the literature, to a few primitives that are carried out in constant time on
sufficiently small trees. The result is extended to trees of arbitrary size,
achieving *2n + O(n / polylog(n))* bits of space. The redundancy
is significantly lower than any previous proposal,
and the data structure is easily implemented.