Skip Navigation

The Computer Journal 2000 43(4):290-300; doi:10.1093/comjnl/43.4.290
© 2000 by British Computer Society
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (5)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Xiang, L.
Right arrow Articles by Akl, S. G.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Generating Regular k-ary Trees Efficiently

Limin Xiang1, Kazuo Ushijima1 and Selim G. Akl2

1 Department of Computer Science and Communication Engineering, Kyushu University, 6-10-1 Hakozaki, Higashi-ku, Fukuoka 812-8581, Japan Email: xiang@csce.kyushu-u.ac.jp 2 Department of Computing and Information Science, Queen's University, Kingston, Ontario, Canada K7L 3N6

A recursive algorithm GenWordsR and a non-recursive algorithm GenWordsNR are presented in this paper to generate sequences for regular k-ary trees efficiently. They are compared with some of the previous recursive and non-recursive algorithms for this problem that were found in the literature. When the average number of recursive calls is used as a measure of the time complexity of recursive algorithms for generating k-ary trees, O(k) calls for a k-ary tree is the bestresult in the previous recursive algorithms, while O(1/k) calls for a k-ary tree is needed by GenWordsR. When the average number of comparisons is used as a measure of the time complexity of non-recursive algorithms for generating k-ary trees, GenWordsNR outperforms the previous non-recursive algorithms. As k increases, the number (and the average number) of comparisons performed by GenWordsNR tends to 66% that of the best previous non-recursive algorithms.

Received 30 March, 2000. Revised 24 August, 2000.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.