Ranking and Unranking of 2-3 Trees

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 space.