6533b81ffe1ef96bd1278535
RESEARCH PRODUCT
Ranking and unrankingk-ary trees with a 4k –4 letter alphabet
Jean PalloVincent Vajnovszkisubject
CombinatoricsDiscrete mathematicsSequenceCardinalityBinary treeEncoding (memory)Weight-balanced treeAlphabetMathematicsZaksRanking (information retrieval)description
Abstract The problem of the direct generation in A-order of binary trees was stated by Zaks in 1980. In 1988 Roelants van Baronaigien and Ruskey gave a solution for k-ary trees with n internal nodes using an encoding sequence of kn+1 integers between 1 and n. Vajnovszki and Pallo improved this result for binary trees in 1994 using words of length n–1 on a four letter alphabet. Recently Korsh generalized the Vajnovszki and Pallo’s generating algorithm to k-ary trees using an alphabet whose cardinality depends on k but not on n. We give in this paper ranking and unranking algorithms for k-ary trees using the Korsh’s encoding scheme.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1997-05-01 | Journal of Information and Optimization Sciences |