A binary tree coding scheme is a bijection mapping a set of binary trees to a set of integer tuples called codewords. One problem considered in the literature is that of listing the codewords for n-node binary trees, such that successive codewords represent trees differing by a single rotation, a standard operation for rebalancing binary search trees. Then, the codeword sequence corresponds to an Hamiltonian path in the rotation graph Rn of binary trees, where each node is labelled with an n-node binary tree, and an edge connects two nodes when their trees differ by a single rotation. A related problem is finding a shortest path between two nodes in Rn, which reduces to the problem of transforming one binary tree into another using a minimum number of rotations. Yet a third problem is determining properties of the rotation graph. Our work addresses these three problems.
Doctor of Philosophy (Ph.D.)
College of Arts and Sciences
Department of Computer Science
Written permission granted by copyright holder to the University of Central Florida Libraries to digitize and distribute for nonprofit, educational purposes.
Length of Campus-only Access
Doctoral Dissertation (Open Access)
Rogers, Rodney O., "Finding paths in the rotation graph of binary trees" (1996). Retrospective Theses and Dissertations. 3063.