Fully-Functional Static and Dynamic Succinct Trees

Gonzalo Navarro, Kunihiko Sadakane

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…