Restricted rotation distance between binary trees.

DOI10.1016/S0020-0190(02)00315-0MaRDI QIDQ1853166zbMATH OpenOpenAlexFDO

Authors Sean Cleary

Publication date 21 January 2003

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(02)00315-0

zbMATH Keywords

Algorithms and data structuresBinary treesRotation distance

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Review text

Restricted rotation distance between pairs of rooted binary trees measures differences in tree shape and is related to rotation distance. In restricted rotation distance, the rotations used to transform the trees are allowed to be only of two types. Restricted rotation distance is larger than rotation distance, since there are only two permissible locations to rotate, but is much easier to compute and estimate. We obtain linear upper and lower bounds for restricted rotation distance in terms of the number of interior nodes in the trees. Further, we describe a linear-time algorithm for estimating the restricted rotation distance between two trees and for finding a sequence of rotations which realizes that estimate. The methods use the metric properties of the abstract group known as Thompson's group \(F\).

Recommendations

• Bounding restricted rotation distance
• BOUNDING RIGHT-ARM ROTATION DISTANCES
• \(k\)-restricted rotation distance between binary trees
• Distributions of restricted rotation distances
• Restricted rotation distance between k-ary trees

Cites work

• A note on some tree similarity measures
• An efficient upper bound of the rotation distance of binary trees
• An infinite-dimensional torsion-free \(\text{FP}_{\infty}\) group
• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 67429 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1418487 (Why is no real title available?)
• scientific article; zbMATH DE number 1439421 (Why is no real title available?)
• Introductory notes on Richard Thompson's groups
• Metrics and embeddings of generalizations of Thompson's group F
• On the upper bound on the rotation distance of binary trees
• Quasi-isometrically embedded subgroups of Thompson's group \(F\)
• Rotation Distance, Triangulations, and Hyperbolic Geometry

Cited in

(21)

• Right-arm rotation distance between binary trees
• Bounding restricted rotation distance
• Root-restricted Kleenean rotations
• A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations
• A direct algorithm for restricted rotation distance
• Generators and normal forms of Richard Thompson's group \(F\) and the four-color theorem
• Effective splaying with restricted rotations
• A metric for rooted trees with unlabeled vertices based on nested parentheses
• Distributions of restricted rotation distances
• scientific article; zbMATH DE number 7527483 (Why is no real title available?)
• BOUNDING RIGHT-ARM ROTATION DISTANCES
• An efficient algorithm for estimating rotation distance between two binary trees
• Algorithms and Data Structures
• Restricted rotation distance between k-ary trees
• Shallow-rotation distance via forest representations
• Efficient lower and upper bounds of the diagonal-flip distance between triangulations
• \(k\)-restricted rotation distance between binary trees
• On the rotation distance between binary trees
• Refined upper bounds for right-arm rotation distances
• Weak associativity and restricted rotation
• Rotation distance is fixed-parameter tractable

This page was built for publication: Restricted rotation distance between binary trees.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853166)