2016/10/19 by Jarek Duda, Duda, Jarek
Computer Science · Engineering · Physics and Astronomy · #Advanced Data Processing Techniques #Advanced Database Systems and Queries #Computational Drug Discovery Methods #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Scientific Research and Discoveries #Statistical and Computational Modeling
paper · pdf · doi:10.48550/arxiv.1610.06023
openalex publication_date 2016/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Tree rotations (left and right) are basic local deformations allowing to transform between two unlabeled binary trees of the same size. Hence, there is a natural problem of practically finding such transformation path with low number of rotations, the optimal minimal number is called the rotation distance. Such distance could be used for instance to quantify similarity between two trees for various machine learning problems, for example to compare hierarchical clusterings or arbitrarily chosen spanning trees of two graphs, like in SMILES notation popular for describing chemical molecules. There will be presented inexpensive practical greedy algorithm for finding a short rotation path, optimality of which has still to be determined. It uses introduced partial order for binary trees of the same size: t1 ≤ t2 iff t2 can be obtained from t1 by a sequence of only right rotations. Intuitively, the shortest rotation path should go through the least upper bound or the greatest lower bound for this partial order. The algorithm finds a path through candidates for both points in representation of binary tree as stack graph: describing evolution of content of stack while processing a formula described by a given binary tree. The article is accompanied with Mathematica implementation of all used procedures (Appendix).