Succinct Ordinal Trees Based on Tree Covering
Various methods have been used to represent a tree on 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. [2006], that supports all the navigational operations supported by various succinct tree representations while requiring only 2n + o( n) bits. It also supports efficient level-order traversal, a useful ordering previously supported only with a very limited set of operations. 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 or depth first unary degree sequence in O(f(n)) time, using at most n/f(n) + o(n) additional bits, for any f(n) in O(lg n) and Omega(1).
ordinal trees tree covering succinct data structures