Ranking and Unranking of 2-3 Trees
- 1 August 1982
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 11 (3) , 582-590
- https://doi.org/10.1137/0211049
Abstract
In this paper we consider the generating, ranking, and unranking of 2-3 trees with n keys. We propose a linear ordering among these trees. The problem of ranking is to determine the rank of a given tree in this ordering, while unranking means constructing the tree of a given rank. The main result is that ranking and unranking can be done in O(n) time after a preprocessing step that takes O(n 2) time and spaceKeywords
This publication has 8 references indexed in Scilit:
- Constant Time Generation of Rooted TreesSIAM Journal on Computing, 1980
- Lexicographic generation of ordered treesTheoretical Computer Science, 1980
- Generating Trees and Other Combinatorial Objects LexicographicallySIAM Journal on Computing, 1979
- Ranking and Listing Algorithms for k-Ary TreesSIAM Journal on Computing, 1978
- Generating t-Ary Trees LexicographicallySIAM Journal on Computing, 1978
- Generating Binary Trees LexicographicallySIAM Journal on Computing, 1977
- A unified setting for sequencing, ranking, and selection algorithms for combinatorial objectsAdvances in Mathematics, 1977
- On the ordering, ranking, and random generation of basic combinatorial setsPublished by Springer Nature ,1977