Representation of ordered trees with a given degree distribution (Q2656174)

In this article the author proposes a new succinct data structure that stores an ordered tree \(T\) with \(n\) nodes using \(\log \mathcal{N}(\overrightarrow{n})+O(n/\log^t n)\) bits for every constant \(t\), were \(\mathcal{N}(\overrightarrow{n})\) is the number of trees with degree distribution \(\overrightarrow{n}\). This new structure is a generalization of the aB-tree structure introduced by M. Pătrașcu. The querying of the structure requires a constant time. The proposed structure uses less space compared to two other similar structures for storing ordered trees (first introduced by \textit{J. Jansson} et al. [J. Comput. Syst. Sci. 78, No. 2, 619--631 (2012; Zbl 1242.68083)] and second introduced by \textit{G. Navarro} and \textit{K. Sadakane} [ACM Trans. Algorithms 10, No. 3, Article No. 16, 39 p. (2014; Zbl 1333.68084)]).