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.

A correspondence between n-node binary trees and triangulations of (n+2)-gons allows labelling nodes of Rn, with triangulations, where adjacent triangulations differ by a single diagonal flip. It has been proven, using properties of triangulations, that Rn is Hamiltonian, and that its diameter is bounded above by 2n-6 for n ≥ 11. In Chapter Three we use triangulations to show that the radius of Rn, is n-1; to characterize the n+2 nodes in the center; to show that Rn is the union of n+2 copies of Rn-1; and to prove that Rn is (n-1)-connected. We also introduce the skeleton graph RSn of Rn, and give additional properties of both graphs.

In Chapter Four, we give an algorithm, OzLex, which, for each of many different coding schemes, generates 2n-1 different sequences of codewords for n-node binary trees. We also show that, for every n ≥ 4, all such sequences combined represent 2n Hamiltonian paths in Rn. In Appendix Two, we modify OzLex to create TransOx, an algorithm which generates (n+2)2n sequences of codewords from a single coding scheme, and prove that, for n ≥ 5, the sequences represent (n+2)2n-1 Hamiltonian paths.

The distance between extreme nodes in Rn is the diameter of the graph. In Chapter Five, we give properties of extreme nodes in terms of their corresponding triangulations; Appendix One contains additional related information. We present two heuristics, based on flipping diagonals, that find a path between two nodes in Rn: Findpath-1, in O(n log n) time; and FindPath-2, in 0(n2 log n) time. Each computes paths with less than twice the minimum length. We also identify a class of triangulation pairs where Findpath-2 significantly outperforms FindPath-1.

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

Accessibility Status

Searchable text

Download

Share

COinS