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.
Abstract:
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?)
Pages: ???-???.
-
Vincent Vajnovszki,
Generating a Gray code for P-sequences,
J. Mathematical Modelling and Algorithms,
1 (2002) 31-41.
Back
to Frank Ruskey's publication list.