  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 a number of operations on the tree can be
supported in constant time under the word-RAM model. However the data
structures are complicated and difficult to dynamize. 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. Our data structure builds on the range min-max tree to
achieve $2n+O(n/\log n)$ bits of space and $O(\log n)$ time for all the
operations. We also propose an improved data structure using $2n+O(n\log\log
n/\log n)$ bits and improving the time to the optimal $O(\log n/\log \log n)$
for most operations. Furthermore, we support sophisticated operations that
allow attaching and detaching whole subtrees, in time $\Order(\log^{1+\epsilon}
n / \log\log n)$. Our techniques are of independent interest. One allows
representing dynamic bitmaps and sequences supporting rank/select and indels,
within zero-order entropy bounds and optimal time $O(\log n / \log\log n)$ for
all operations on bitmaps and polylog-sized alphabets, and $O(\log n \log
\sigma / (\log\log n)^2)$ on larger alphabet sizes $\sigma$. This improves upon
the best existing bounds for entropy-bounded storage of dynamic sequences,
compressed full-text self-indexes, and compressed-space construction of the
Burrows-Wheeler transform.
