Succinct Ordinal Trees Based on Tree Covering

Various methods have been used to represent a tree of

n

nodes in essentially the information-theoretic minimum space while supporting various navigational operations in constant time, but different representations usually support different operations. Our main contribution is a succinct representation of ordinal trees, based on that of Geary et al. (7), that supports all the navigational operations supported by various succinct tree representations while requiring only 2

n

 + 

o

(

n

) bits. It also supports efficient level-order traversal, a useful ordering previously supported only with a very limited set of operations (8).

Our second contribution expands on the notion of a single succinct representation supporting more than one traversal ordering, by showing that our method supports two other encoding schemes as abstract data types. In particular, it supports extracting a word (

$O(\lg n)$

bits) of the balanced parenthesis sequence (11) or depth first unary degree sequence (3;4) in

O

(

f

(

n

)) time, using at most

n

/

f

(

n

) + 

o

(

n

) additional bits, for any

f

(

n

) in

$O(\lg n)$

and

Ω

(1).