Experimental and Theoretical Approaches for Efficient Tree Distance Algorithms

Cuny City College, New York NY

Investigators

Abstract

This project has involves research on several fronts in binary trees and algorithms for their efficient use. Rotations are small changes to binary tree structures used in balancing and optimizing search trees for efficient searching. The rotation distance between two trees is the minimal number of such small changes required to transform one tree into another. There are no known algorithms for computing rotation distances effectively, and even precise bounds on rotation distance are difficult to obtain. This project develops methods for improving understanding of rotation distances and algorithms for computing or estimating them. This research involves experiments to understand the general properties of rotation distances, as well as developing abstract methods for describing rotation distances based upon connections between rotation distances and geometric methods in group theory. This project seeks to improve methods and understanding of binary trees and relevant algorithms. Binary trees are a fundamental structure, underlying efficient storage of data sets for quick retrieval of items. The amount of data routinely used in modern scientific and engineering settings is often staggeringly large. Biological data sets, for example, are often gigabytes of data. When working with large data sets, the efficiency of methods used to analyze the data is of crucial importance- many questions which are immediate for small data sets are far beyond the capability of even today's most powerful computers for even moderate-sized data sets. Careful organization of large data sets is essential for productive investigation