
doi: 10.1137/0215073
In this paper, we consider the problem of generating, ranking, and unranking of AVL-trees with n leaves. We represent AVL-trees by integer- pair sequences, called LDP-sequences. Then we propose a linear ordering among these sequences, i.e., among the AVL-trees. The problem of ranking is to determine the oder number (rank) of a given tree in this ordering, unranking means constructing the tree of a given rank. The main result is that ranking and unranking can be done in O(n log\({}^ 2n)\) and O(n log\({}^ 3n)\) time, respectively, after a preprocessing step that takes \(O(n^ 2\log n)\) time.
algorithm, AVL-trees, ranking, Analysis of algorithms and problem complexity, Graph theory (including graph drawing) in computer science, unranking, Trees
algorithm, AVL-trees, ranking, Analysis of algorithms and problem complexity, Graph theory (including graph drawing) in computer science, unranking, Trees
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 13 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
