Succinct ordinal trees based on tree covering
Meng He, J. Ian Munro, Srinivasa Rao Satti · ACM Transactions on Algorithms · 2012
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 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. 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 Ω(1).