Universal succinct representations of trees?

*(English)*Zbl 1248.68168
Albers, Susanne (ed.) et al., Automata, languages and programming. 36th international colloquium, ICALP 2009, Rhodes, Greece, July 5–12, 2009. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-02926-4/pbk). Lecture Notes in Computer Science 5555, 451-462 (2009).

Summary: We consider the succinct representation of ordinal and cardinal trees on the RAM with logarithmic word size. Given a tree \(T\), our representations support the following operations in \(O(1)\) time: (i) \(\mathrm{BP-substring}(i,b)\), which reports the substring of length \(b\) bits (\(b\) is at most the wordsize) beginning at position \(i\) of the balanced parenthesis representation of \(T\), (ii) \(\mathrm{DFUDS-substring}(i,b)\), which does the same for the depth first unary degree sequence representation, and (iii) a similar operation for tree-partition based representations of \(T\). We give:

– an asymptotically space-optimal \(2n + o(n)\) bit representation of \(n\)-node ordinal trees that supports all the above operations with \(b = \Theta (\log n)\), answering an open question from [M. He, J. I. Munro and S. S. Rao, Lect. Notes Comput. Sci. 4596, 509–520 (2007; Zbl 1171.68436)].

– an asymptotically space-optimal \(C(n,k) + o(n)\)-bit representation of \(k\)-ary cardinal trees, that supports (with \(b = \Theta(\sqrt{\log n}))\) the operations (ii) and (iii) above, on the ordinal tree obtained by removing labels from the cardinal tree, as well as the usual label-based operations. As a result, we obtain a fully-functional cardinal tree representation with the above space complexity. This answers an open question from [R. Raman, V. Raman and S. S. Rao, in: Proceedings of the 13th annual ACM-SIAM symposium on discrete algorithms, SODA’02, 233–242 (2002; Zbl 1093.68582)].

Our new representations are able to simultaneously emulate the BP, DFUDS and partitioned representations using a single instance of the data structure, and thus aim towards universality. They not only support the union of all the ordinal tree operations supported by these representations, but will also automatically inherit any new operations supported by these representations in the future.

For the entire collection see [Zbl 1166.68001].

– an asymptotically space-optimal \(2n + o(n)\) bit representation of \(n\)-node ordinal trees that supports all the above operations with \(b = \Theta (\log n)\), answering an open question from [M. He, J. I. Munro and S. S. Rao, Lect. Notes Comput. Sci. 4596, 509–520 (2007; Zbl 1171.68436)].

– an asymptotically space-optimal \(C(n,k) + o(n)\)-bit representation of \(k\)-ary cardinal trees, that supports (with \(b = \Theta(\sqrt{\log n}))\) the operations (ii) and (iii) above, on the ordinal tree obtained by removing labels from the cardinal tree, as well as the usual label-based operations. As a result, we obtain a fully-functional cardinal tree representation with the above space complexity. This answers an open question from [R. Raman, V. Raman and S. S. Rao, in: Proceedings of the 13th annual ACM-SIAM symposium on discrete algorithms, SODA’02, 233–242 (2002; Zbl 1093.68582)].

Our new representations are able to simultaneously emulate the BP, DFUDS and partitioned representations using a single instance of the data structure, and thus aim towards universality. They not only support the union of all the ordinal tree operations supported by these representations, but will also automatically inherit any new operations supported by these representations in the future.

For the entire collection see [Zbl 1166.68001].

##### MSC:

68P05 | Data structures |