If the Dyck words are arranged according to the lexicographical order, then ranking means to determine the rank, i. e. the position, of a Dyck word. Unranking creates the Dyck word from its position.
We present a ranking and an unranking algorithm for the generalized Dyck language. Given a Dyck word, the ranking algorithm reads a prefix as short as possible to compute the rank. Thus, this algorithm is optimal. The unranking algorithm creates the Dyck word symbol by symbol from left to right.
Further, we analyze the ranking algorithm. For the computation of the rank of a Dyck word for arbitrary relation, we compute the moments of the random variable describing the length of the prefix to be read. No computation is necessary for the analysis of the unranking algorithm, because the whole Dyck word has to be created.
The generalized Dyck language can be used for the coding of trees. Not only the shape of the tree is coded but also its labels of the nodes and/or edges. The algorithms discussed here can be used for the ranking and unranking of different types of trees. With a random number generator and the unranking algorithm we are able to generate random trees with diverse properties. Some classes of labelled trees will be discussed.
Keywords: Dyck language, random trees, ranking, unranking,
lexicographical order, one-to-one correspondence, average-case analysis.
The following versions are available: