You are here
Finding paths in the rotation graph of binary trees
 Date Issued:
 1996
 Abstract/Description:
 University of Central Florida College of Arts and Sciences Thesis; 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 nnode 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 nnode 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.
Title:  Finding paths in the rotation graph of binary trees. 
38 views
15 downloads 

Name(s): 
Rogers, Rodney O., Author Dutton, Ronald D., Committee Chair Arts and Sciences, Degree Grantor 

Type of Resource:  text  
Date Issued:  1996  
Publisher:  University of Central Florida  
Language(s):  English  
Abstract/Description:  University of Central Florida College of Arts and Sciences Thesis; 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 nnode 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 nnode 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.  
Identifier:  CFR0000193 (IID), ucf:52941 (fedora)  
Note(s): 
19960501 Ph.D. Computer Science Doctorate This record was generated from author submitted information. Electronically reproduced by the University of Central Florida from a book held in the John C. Hitt Library at the University of Central Florida, Orlando. 

Subject(s): 
Arts and Sciences  Dissertations Academic Dissertations Academic  Arts and Sciences 

Persistent Link to This Record:  http://purl.flvc.org/ucf/fd/CFR0000193  
Restrictions on Access:  public  
Host Institution:  UCF 