Abstract
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.
Graduation Date
1996
Semester
Summer
Advisor
Dutton, Ronald
Degree
Doctor of Philosophy (Ph.D.)
College
College of Arts and Sciences
Department
Department of Computer Science
Degree Program
Computer Science
Format
Language
English
Rights
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
None
Access Status
Doctoral Dissertation (Open Access)
Identifier
DP0000193
STARS Citation
Rogers, Rodney O., "Finding paths in the rotation graph of binary trees" (1996). Retrospective Theses and Dissertations. 3063.
https://stars.library.ucf.edu/rtd/3063