Key points are not available for this paper at this time.
An ordinal tree is an arbitrary rooted tree where the children of each node are ordered. Succinct representations for ordinal trees with efficient query support have been extensively studied. The best previously known result is due to Geary et al. 2004b, pages 1--10. The number of bits required by their representation for an n -node ordinal tree T is 2 n + o ( n ), whose first-order term is information-theoretically optimal. Their representation supports a large set of O (1)-time queries on T . Based upon a balanced string of 2 n parentheses, we give an improved 2 n + o ( n )-bit representation for T . Our improvement is two-fold: First, the set of O (1)-time queries supported by our representation is a proper superset of that supported by the representation of Geary, Raman, and Raman. Second, it is also much easier for our representation to support new queries by simply adding new auxiliary strings.
Lu et al. (Sun,) studied this question.