Generating Binary Trees by Transpositions
Frank Ruskey, Department of Computer Science,
University of Victoria, Canada.
Andrzej Proskurowski, Department of Information and
Computer Science, University of Oregon, USA.
Let T(n) denote the set of all bitstrings with n 1's
and n 0's that satisfy the property that in every prefix the number
of 0's does not exceed the number of 1's. This is a well known
representation of binary trees.
We consider algorithms for generating the elements of T(n)
that satisfy one of the following constraints:
(a) successive bitstrings differ by the transposition of two bits, or
(b) successive bitstrings differ by the transposition of two adjacent bits.
In case (a) a constant average time generation algorithm is presented.
In case (b) we show that such generation is possible if and only if
n is even or n < 5.
A constant average time algorithm is presented in this case as well.
- The postscript file is 217,892 bytes,
the dvi file is 78,312 bytes.
- Appeared in Journal of Algorithms, 11 (1990) 68-84.
- An implementation is available.
- The algorithms are used in the
"Object Server", in the
trees -- Binary trees by rotations section.
- This paper superceeds our earlier paper:
A. Proskurowski and F. Ruskey, Gray Codes for Binary Trees,
Journal of Algorithms, 6 (1985) 225-238.
Selected papers that refer to this paper:
Andre C. Drummond and Nelson L.S. da Fonseca,
A Fixed-Parameter Tractable Approach for the Wavelength
Assignment Problem in Transparent Networks,
IEEE Communications Letters, 12 (2008) 523-525.
William D. May and John C. Wierman,
Algorithms for Non-crossing Partitons,
Combinatorics, Probability and Computing,
Volume ??, (200?)
Generating a Gray code for P-sequences,
J. Mathematical Modelling and Algorithms,
1 (2002) 31-41.
to Frank Ruskey's publication list.