###
Succinct Trees in Practice

####
Diego Arroyuelo, Rodrigo Cánovas, Gonzalo Navarro, and
Kunihiko Sadakane

We implement and compare the major current techniques for representing general
trees in succinct form. This is important because a general tree of *n* nodes
is usually represented in pointer form, requiring *O(n log n)* bits, whereas
the succinct representations we study require just *2n+o(n)* bits and carry
out many sophisticated operations in constant time. Yet, there is no
exhaustive study in the literature comparing the practical magnitudes of the
*o(n)*-space and the *O(1)*-time terms. The techniques can be classified into
three broad trends: those based on BP (balanced parentheses in preorder),
those based on DFUDS (depth-first unary degree sequence), and those based on
LOUDS (level-ordered unary degree sequence). BP and DFUDS require a balanced
parentheses representation that supports the core operations *findopen*,
*findclose*, and *enclose*, for which we implement and compare three
major algorithmic proposals. All the tree representations require also core
operations *rank* and *select* on bitmaps, which are already well
studied in the literature. We show how to predict the time and space
performance of most variants via combining these core operations, and also
study some operations for which specialized implementations exist. This is
especially relevant for a recent proposal (K. Sadakane and G. Navarro,
*SODA'10*) which, although belonging to class BP, deviates from the main
techniques in some cases in order to achieve constant time for the widest
range of operations. We experiment over various types of real-life trees and
of traversals, and conclude that the latter technique stands out as an
excellent practical combination of space occupancy, time performance, and
functionality, whereas others are still interesting in some
limited-functionality niches.