Generation of Neuronal Trees by a New Three Letters Encoding

Abstract

A neuronal tree is a rooted tree with n leaves whose each internal node has at least two children; this class not only is defined based on the structure of dendrites in neurons, but also refers to phylogenetic trees or evolutionary trees. More precisely, neuronal trees are rooted-multistate phylogenetic trees whose size is defined as the number of leaves. In this paper, a new encoding over an alphabet of size 3 (minimal cardinality) is introduced for representing the neuronal trees with a given number of leaves. This encoding is used for generating neuronal trees with n leaves in A-order with constant average time and O(n) time complexity in the worst case. Also, new ranking and unranking algorithms are presented in time complexity of O(n) and O(n log n), respectively.