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

PDF

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

Download

Share

COinS