Experimental and Theoretical Approaches for Efficient Tree Distance Algorithms

这个项目涉及对二叉树的几个方面的研究，以及有效使用二叉树的算法。轮换是对二叉树结构的微小更改，用于平衡和优化搜索树以实现高效搜索。两棵树之间的旋转距离是将一棵树转换为另一棵树所需的最小数量的微小变化。目前还没有已知的有效计算旋转距离的算法，甚至很难获得旋转距离的精确界限。这个项目开发了提高对旋转距离的理解的方法，以及计算或估计它们的算法。该研究通过实验了解旋转距离的一般性质，并基于旋转距离与群论中几何方法之间的联系来开发描述旋转距离的抽象方法，旨在改进二叉树及其相关算法的方法和理解。二叉树是一种基本结构，为快速检索项目提供了高效的数据集存储基础。现代科学和工程环境中经常使用的数据量往往大得惊人。例如，生物数据集通常是千兆字节的数据。在处理大数据集时，用于分析数据的方法的效率至关重要--许多问题对于小数据集来说是迫在眉睫的，甚至远远超出了当今最强大的计算机即使是中等大小的数据集的能力。仔细组织大型数据集对于富有成效的调查至关重要

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