discrete mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...

and

theoretical computer science Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...

, the rotation distance between two

binary tree In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as the ''left child'' and the ''right child''. That is, it is a ''k''-ary tree with . A recursive definition using set theor ...

s with the same number of nodes is the minimum number of

tree rotation In discrete mathematics, tree rotation is an operation on a binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. It is used to change the shape ...

s needed to reconfigure one tree into another. Because of a combinatorial equivalence between binary trees and triangulations of convex polygons, rotation distance is equivalent to the flip distance for triangulations of

convex polygon In geometry, a convex polygon is a polygon that is the boundary of a convex set. This means that the line segment between two points of the polygon is contained in the union of the interior and the boundary of the polygon. In particular, it is ...

s. Rotation distance was first defined by Karel Čulík II and Derick Wood in 1982. Every two -node binary trees have a rotation distance of at most for all , and some pairs of trees have exactly this distance. The

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations ...

of computing the rotation distance is unknown.

Definition

is a structure consisting of a set of nodes, one of which is designated as the root node, in which each remaining node is either the ''left child'' or ''right child'' of some other node, its ''parent'', and in which following the parent links from any node eventually leads to the root node. (In some sources, the nodes described here are called "internal nodes", there exists another set of nodes called "external nodes", each internal node is required to have exactly two children, and each external node is required to have zero children. The version described here can be obtained by removing all the external nodes from such a tree.) For any node in the tree, there is a ''subtree'' of the same form, rooted at and consisting of all the nodes that can reach by following parent links. Each binary tree has a left-to-right ordering of its nodes, its inorder traversal, obtained by recursively traversing the left subtree (the subtree at the left child of the root, if such a child exists), then listing the root itself, and then recursively traversing the right subtree. In a

binary search tree In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a Rooted tree, rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left ...

, each node is associated with a search key, and the left-to-right ordering is required to be consistent with the order of the keys. A

is an operation that changes the structure of a binary tree without changing its left-to-right ordering. Several

self-balancing binary search tree In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.Donald ...

data structure In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...

s use these rotations as a primitive operation in their rebalancing algorithms. A rotation operates on two nodes and , where is the parent of , and restructures the tree by making be the parent of and taking the place of in the tree. To free up one of the child links of and make room to link as a child of , this operation may also need to move one of the children of to become a child of . There are two variations of this operation, a ''right rotation'' in which begins as the left child of and ends as the right child of , and a ''left rotation'' in which begins as the right child of and ends as the left child of . Any two trees that have the same left-to-right sequence of nodes may be transformed into each other by a sequence of rotations. The rotation distance between the two trees is the number of rotations in the shortest possible sequence of rotations that performs this transformation. It can also be described as the shortest path distance in a ''rotation graph'', a graph that has a vertex for each binary tree on a given left-to-right sequence of nodes and an edge for each rotation between two trees. This rotation graph is exactly the graph of vertices and edges of an associahedron.

Equivalence to flip distance

Given a family of triangulations of some geometric object, a ''flip'' is an operation that transforms one triangulation to another by removing an edge between two triangles and adding the opposite diagonal to the resulting quadrilateral. The flip distance between two triangulations is the minimum number of flips needed to transform one triangulation into another. It can also be described as the shortest path distance in a '' flip graph'', a graph that has a vertex for each triangulation and an edge for each flip between two triangulations. Flips and flip distances can be defined in this way for several different kinds of triangulations, including triangulations of sets of points in the

Euclidean plane In mathematics, a Euclidean plane is a Euclidean space of Two-dimensional space, dimension two, denoted \textbf^2 or \mathbb^2. It is a geometric space in which two real numbers are required to determine the position (geometry), position of eac ...

, triangulations of

polygon In geometry, a polygon () is a plane figure made up of line segments connected to form a closed polygonal chain. The segments of a closed polygonal chain are called its '' edges'' or ''sides''. The points where two edges meet are the polygon ...

s, and triangulations of abstract

manifold In mathematics, a manifold is a topological space that locally resembles Euclidean space near each point. More precisely, an n-dimensional manifold, or ''n-manifold'' for short, is a topological space with the property that each point has a N ...

s. There is a one-to-one correspondence between triangulations of a given

, with a designated root edge, and binary trees, taking triangulations of -sided polygons into binary trees with nodes. In this correspondence, each triangle of a triangulation corresponds to a node in a binary tree. The root node is the triangle having the designated root edge as one of its sides, and two nodes are linked as parent and child in the tree when the corresponding triangles share a diagonal in the triangulation. Under this correspondence, rotations in binary trees correspond exactly to flips in the corresponding triangulations. Therefore, the rotation distance on -node trees corresponds exactly to flip distance on triangulations of -sided convex polygons.

Maximum value

define the "right spine" of a binary tree to be the path obtained by starting from the root and following right child links until reaching a node that has no right child. If a tree has the property that not all nodes belong to the right spine, there always exists a right rotation that increases the length of the right spine. For, in this case, there exists at least one node on the right spine that has a left child that is not on the right spine. Performing a right rotation on and adds to the right spine without removing any other node from it. By repeatedly increasing the length of the right spine, any -node tree can be transformed into the unique tree with the same node order in which all nodes belong to the right spine, in at most steps. Given any two trees with the same node order, one can transform one into the other by transforming the first tree into a tree with all nodes on the right spine, and then reversing the same transformation of the second tree, in a total of at most steps. Therefore, as proved, the rotation distance between any two trees is at most . By considering the problem in terms of flips of convex polygons instead of rotations of trees, were able to show that the rotation distance is at most . In terms of triangulations of convex polygons, the right spine is the sequence of triangles incident to the right endpoint of the root edge, and the tree in which all vertices lie on the spine corresponds to a

fan triangulation In computational geometry, a fan triangulation is a simple way to Polygon triangulation, triangulate a polygon by choosing a Vertex (geometry), vertex and drawing Edge (geometry), edges to all of the other vertices of the polygon. Not every poly ...

for this vertex. The main idea of their improvement is to try flipping both given triangulations to a fan triangulation for any vertex, rather than only the one for the right endpoint of the root edge. It is not possible for all of these choices to simultaneously give the worst-case distance from each starting triangulation, giving the improvement. also used a geometric argument to show that, for infinitely many values of , the maximum rotation distance is exactly . They again use the interpretation of the problem in terms of flips of triangulations of convex polygons, and they interpret the starting and ending triangulation as the top and bottom faces of a

convex polyhedron In geometry, a polyhedron (: polyhedra or polyhedrons; ) is a three-dimensional figure with flat polygonal faces, straight edges and sharp corners or vertices. The term "polyhedron" may refer either to a solid figure or to its boundary su ...

with the convex polygon itself interpreted as a Hamiltonian circuit in this polyhedron. Under this interpretation, a sequence of flips from one triangulation to the other can be translated into a collection of

tetrahedra In geometry, a tetrahedron (: tetrahedra or tetrahedrons), also known as a triangular pyramid, is a polyhedron composed of four triangular Face (geometry), faces, six straight Edge (geometry), edges, and four vertex (geometry), vertices. The tet ...

that triangulate the given three-dimensional polyhedron. They find a family of polyhedra with the property that (in three-dimensional

hyperbolic geometry In mathematics, hyperbolic geometry (also called Lobachevskian geometry or János Bolyai, Bolyai–Nikolai Lobachevsky, Lobachevskian geometry) is a non-Euclidean geometry. The parallel postulate of Euclidean geometry is replaced with: :For a ...

) the polyhedra have large volume, but all tetrahedra inside them have much smaller volume, implying that many tetrahedra are needed in any triangulation. The binary trees obtained from translating the top and bottom sets of faces of these polyhedra back into trees have high rotation distance, at least . Subsequently, provided a proof that for all , the maximum rotation distance is exactly . Pournin's proof is combinatorial, and avoids the use of hyperbolic geometry.

Computational complexity

As well as defining rotation distance, asked for the

of computing the rotation distance between two given trees. The existence of short rotation sequences between any two trees implies that testing whether the rotation distance is at most belongs to the

complexity class In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...

NP, but it is not known to be

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

, nor is it known to be solvable in

polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

. The rotation distance between any two trees can be lower bounded, in the equivalent view of polygon triangulations, by the number of diagonals that need to be removed from one triangulation and replaced by other diagonals to produce the other triangulation. It can also be upper bounded by twice this number, by partitioning the problem into subproblems along any diagonals shared between both triangulations and then applying the method of to each subproblem. This method provides an

approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...

for the problem with an

approximation ratio In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...

of two. A similar approach of partitioning into subproblems along shared diagonals leads to a fixed-parameter tractable algorithm for computing the rotation distance exactly. Determining the complexity of computing the rotation distance exactly without parameterization remains unsolved, and the best algorithms currently known for the problem run in exponential time.

Variants

Though the complexity of rotation distance is unknown, there exists several variants for which rotation distance can be solved in polynomial time. In

abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures, which are set (mathematics), sets with specific operation (mathematics), operations acting on their elements. Algebraic structur ...

, each element in Thompson's group F has a

presentation A presentation conveys information from a speaker to an audience. Presentations are typically demonstrations, introduction, lecture, or speech meant to inform, persuade, inspire, motivate, build goodwill, or present a new idea/product. Presenta ...

using two generators. Finding the minimum length of such a presentation is equivalent to finding the rotation distance between two binary trees with only rotations on the root node and its right child allowed. Fordham's algorithm computes the rotation distance under this restriction in linear time. The algorithm classifies tree nodes into 7 types and uses a lookup table to find the number of rotations required to transform a node of one type into another. The sum of the costs of all transformations is the rotation distance. In two additional variants, one only allows rotations such that the pivot of the rotation is a non-leaf child of the root and the other child of the root is a leaf, while the other only allow rotations on right-arm nodes (nodes that are on the path from the root to its rightmost leaf). Both variants result in a meet semi-lattice, whose structure is exploited to derive a

O(n^2)

algorithm.

References

{{reflist, refs= {{citation , last1=Bonnin , first1=André , last2=Pallo , first2=Jean-Marcel , title=A shortest path metric on unlabeled binary trees , journal=Pattern Recognition Letters , publisher=Elsevier BV , volume=13 , issue=6 , year=1992 , issn=0167-8655 , doi=10.1016/0167-8655(92)90047-4 , pages=411–415 , bibcode=1992PaReL..13..411B {{citation , last1 = Cleary , first1 = Sean , last2 = St. John , first2 = Katherine , author2-link = Katherine St. John , arxiv = 0903.0197 , doi = 10.1016/j.ipl.2009.04.023 , issue = 16 , journal =

Information Processing Letters ''Information Processing Letters'' is a peer review, peer-reviewed scientific journal in the field of computer science, published by Elsevier. The aim of the journal is to enable fast dissemination of results in the field of Data processing, inform ...

, mr = 2541971 , pages = 918–922 , title = Rotation distance is fixed-parameter tractable , volume = 109 , year = 2009, s2cid = 125834 {{citation , last1 = Cleary , first1 = Sean , last2 = St. John , first2 = Katherine , author2-link = Katherine St. John , doi = 10.7155/jgaa.00212 , issue = 2 , journal = Journal of Graph Algorithms and Applications , mr = 2740180 , pages = 385–390 , title = A linear-time approximation for rotation distance , volume = 14 , year = 2010, doi-access = free , arxiv = 0903.0199 {{citation , last1 = Čulík , first1 = Karel II , last2 = Wood , first2 = Derick , author2-link = Derick Wood , doi = 10.1016/0020-0190(82)90083-7 , issue = 1 , journal =

, mr = 678031 , pages = 39–42 , title = A note on some tree similarity measures , volume = 15 , year = 1982 {{citation , last=Fordham , first=Blake , title=Minimal Length Elements of Thompson's Group F , journal=Geometriae Dedicata , publisher=Springer Science and Business Media LLC , volume=99 , issue=1 , year=2003 , issn=0046-5755 , doi=10.1023/a:1024971818319 , pages=179–220 {{citation , last = Lucas , first = Joan M. , doi = 10.1016/j.ipl.2010.04.022 , issue = 12–13 , journal =

, mr = 2667389 , pages = 481–484 , title = An improved kernel size for rotation distance in binary trees , volume = 110 , year = 2010 {{citation , last1=Li , first1=Haohong , last2=Xia , first2=Ge , title=An 𝒪(3.82^k) Time FPT Algorithm for Convex Flip Distance , journal=

Discrete & Computational Geometry '' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational ...

, publisher=Springer Science and Business Media LLC , date=2023-11-05 , pages=44:1–44:14 , issn=0179-5376 , doi=10.1007/s00454-023-00596-9 , url=https://drops.dagstuhl.de/opus/volltexte/2023/17696/ {{citation , last=Pallo , first=Jean Marcel , title=Right-arm rotation distance between binary trees , journal=Information Processing Letters , publisher=Elsevier BV , volume=87 , issue=4 , year=2003 , issn=0020-0190 , doi=10.1016/s0020-0190(03)00283-7 , pages=173–177 {{citation , last = Pournin , first = Lionel , doi = 10.1016/j.aim.2014.02.035 , journal =

Advances in Mathematics ''Advances in Mathematics'' is a peer-reviewed scientific journal covering research on pure mathematics. It was established in 1961 by Gian-Carlo Rota. The journal publishes 18 issues each year, in three volumes. At the origin, the journal aimed ...

, mr = 3197650 , pages = 13–42 , title = The diameter of associahedra , volume = 259 , year = 2014, doi-access = free , arxiv = 1207.6296 {{citation , last1 = Sleator , first1 = Daniel D. , author1-link = Daniel Sleator , last2 = Tarjan , first2 = Robert E. , author2-link = Robert Tarjan , last3 = Thurston , first3 = William P. , author3-link = William Thurston , doi = 10.1090/S0894-0347-1988-0928904-4 , issue = 3 , journal =

Journal of the American Mathematical Society The ''Journal of the American Mathematical Society'' (''JAMS''), is a quarterly peer-reviewed mathematical journal published by the American Mathematical Society. It was established in January 1988. Abstracting and indexing This journal is abs ...

, jstor = 1990951 , mr = 928904 , pages = 647–681 , title = Rotation distance, triangulations, and hyperbolic geometry , volume = 1 , year = 1988, doi-access = free Binary trees Triangulation (geometry) Reconfiguration