Generating Binary Trees by Rotations
Joan
M. Lucas, Department of Computer Science,
SUNY Brockport, USA.
Dominique
Roelants van Baronagien, Department of Computer Science,
University of Victoria, Canada.
Frank
Ruskey, Department of Computer Science,
University of Victoria, Canada.
Abstract:
The rotation graph, G(n),
has vertex set consisting of all binary trees with n nodes.
Two vertices are connected by an edge if a single rotation will
transform one tree into the other. We provide a simpler
proof of a result of Lucas [x] that G(n)
contains a Hamilton path. Our proof deals directly
with the pointer representation of the binary tree.
This proof provides the basis of an algorithm for
generating all binary trees that can be implemented
to run on a pointer machine and to use only constant
time between the output of successive trees.
Ranking and unranking algorithms are developed
for the ordering of binary trees implied by the generation algorithm.
These algorithms have time complexity O(n2)
(arithmetic operations).
We also show strong relationships amongst various
representations of binary trees and amongst binary tree generation
algorithms that have recently appeared in the literature.
- The postscript file is 269,994 bytes,
the dvi file is 80,500 bytes.
- Appeared in Journal of Algorithms, 15 (1993) 343-366.
- An implementation is available.
- The algorithms are used in the
"
Object Server", in the
trees -- Binary trees by rotations section.
- The reference Lucas [x] is to the paper:
Joan M. Lucas, The Rotation Graph is Hamiltonian, Journal
of Algorithms, 9 (1988) 503-535.
- Typos:
- Page 356, Table 1, heading Alg-M:
A [
should be {.
- Page 358, Figure 10, rightmost node in the tree:
The label 004
should be 104.
- This algorithm is presented in Section 7.2.1.6 of
The Art of Computer Programming by Donald Knuth.