Excellence in Research and Innovation for Humanity

Najme Khorasani

Publications

1

Publications

1
9384
Ranking and Unranking Algorithms for k-ary Trees in Gray Code Order
Abstract:
In this paper, we present two new ranking and unranking algorithms for k-ary trees represented by x-sequences in Gray code order. These algorithms are based on a gray code generation algorithm developed by Ahrabian et al.. In mentioned paper, a recursive backtracking generation algorithm for x-sequences corresponding to k-ary trees in Gray code was presented. This generation algorithm is based on Vajnovszki-s algorithm for generating binary trees in Gray code ordering. Up to our knowledge no ranking and unranking algorithms were given for x-sequences in this ordering. we present ranking and unranking algorithms with O(kn2) time complexity for x-sequences in this Gray code ordering
Keywords:
k-ary Tree Generation, Ranking, Unranking, Gray Code.