Restricted rotation distance between binary trees. (Q1853166): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 12:13, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Restricted rotation distance between binary trees. |
scientific article |
Statements
Restricted rotation distance between binary trees. (English)
0 references
21 January 2003
0 references
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\).
0 references
Algorithms and data structures
0 references
Binary trees
0 references
Rotation distance
0 references