Advanced Modeling and Optimization

Abstract for Paper 2 of Volume 5, Number 1, 2003, pp. 27-38

On the generation of P-sequences

H. Ahrabian,
A. Nowzari-Dalini
Department of Mathematics and Computer Science,
Faculty of Science, University of Tehran,
Tehran, Iran

 


Abstract
An efficient algorithm for the generation of P-sequences is presented. P-sequences are integer sequences characterizing all shapes of n-noded binary trees.
This algorithm generates each sequence in B-order with constant average time O(1). The sequences are generated in lexicographical orders.
The ranking and unranking algorithms with O(n) time complexity are also described. Finally, an algorithm for the construction of a binary tree with a linked structure from P-sequence is presented.

Keywords: Binary tree, Recursion, P-sequences, B-order.