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.