Restricted rotation distance between binary trees.
type: Item
instance of: scholarly article
title: Restricted rotation distance between binary trees.
zbMATH Open document ID: 1042.68036
DOI: 10.1016/S0020-0190(02)00315-0
author: Sean Cleary
published in: Information Processing Letters
publication date: 2003-01-21T00:00:00Z
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\).
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68W05
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1856496
zbMATH Keywords: Algorithms and data structures
zbMATH Keywords: Binary trees
zbMATH Keywords: Rotation distance
MaRDI profile type: Publication
cites work: An infinite-dimensional torsion-free \(\text{FP}_{\infty}\) group
cites work: Q4012139
cites work: Quasi-isometrically embedded subgroups of Thompson's group \(F\)
cites work: Metrics and embeddings of generalizations of Thompson's group \(F\)
cites work: Introductory notes on Richard Thompson's groups
cites work: A note on some tree similarity measures
cites work: Q4003861
cites work: Q3772406
cites work: Q4942049
cites work: Q4057549
cites work: On the upper bound on the rotation distance of binary trees
cites work: An efficient upper bound of the rotation distance of binary trees
cites work: Q4949795
cites work: Rotation Distance, Triangulations, and Hyperbolic Geometry
full work available at URL: s0020-0190(02)00315-0
OpenAlex ID: W1972564423
description: scientific article; zbMATH DE number 1856496