Fully-Functional Succinct Trees

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 2 n + o ( n ) bits and a large number of 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 Ω( n log log n / log n ), which cannot be neglected in practice, (2) the hidden constant is also large, (3) the data structures are complicated and difficult to implement, and (4) the techniques do not extend to dynamic trees supporting insertions and deletions of nodes. 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, which are carried out in constant time on sufficiently small trees. The result is then extended to trees of arbitrary size, achieving 2 n + ( n /polylog( n )) bits of space. The redundancy is significantly lower than in any previous proposal, and the data structure is easily implemented. Furthermore, using the same framework, we derive the first fully-functional dynamic succinct trees.

Authors

• Kunihiko Sadakane
• Gonzalo Navarro 0001

Keywords

No keywords are indexed for this paper.