## 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 R _{n} 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 R

_{n}, 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 R_{n}, with triangulations, where adjacent triangulations differ by a single *diagonal flip*. It has been proven, using properties of triangulations, that R_{n} 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 R_{n}, is n-1; to characterize the n+2 nodes in the center; to show that R_{n} is the union of n+2 copies of R_{n-1}; and to prove that R_{n} is (n-1)-connected. We also introduce the skeleton graph RS_{n} of R_{n}, and give additional properties of both graphs.

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

The distance between *extreme* nodes in R_{n} 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 R_{n}: *Findpath*-1, in O(n log n) time; and *FindPath*-2, in 0(n^{2} 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

## 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

## Accessibility Status

Searchable text