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 (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

, the rotation distance between two

binary tree In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...

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 a ...

s. Rotation distance was first defined by Karel Čulík II and

Derick Wood Derick Wood (1940–2010) was an English computer scientist who worked for many years as a professor of computer science in Canada and Hong Kong. He was known for his research in automata theory and formal languages, much of which he published in ...

in 1982. Every two -node binary trees have rotation distance at most , 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 In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once. S ...

, 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 binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and ...

, 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, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...

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 In mathematics, an associahedron is an -dimensional convex polytope in which each vertex corresponds to a way of correctly inserting opening and closing parentheses in a string of letters, and the edges correspond to single application of ...

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 In mathematics, a flip graph is a graph whose vertices are combinatorial or geometric objects, and whose edges link two of these objects when they can be obtained from one another by an elementary operation called a flip. Flip graphs are spec ...

'', 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, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...

, triangulations of

polygon In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed ''polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two toge ...

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 triangulate a polygon by choosing a vertex and drawing edges to all of the other vertices of the polygon. Not every polygon can be triangulated this way, so this method is usuall ...

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 A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...

with the convex polygon itself interpreted as a

Hamiltonian circuit In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

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 (plural: tetrahedra or tetrahedrons), also known as a triangular pyramid, is a polyhedron composed of four triangular faces, six straight edges, and four vertex corners. The tetrahedron is the simplest of all the o ...

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 Bolyai– Lobachevskian geometry) is a non-Euclidean geometry. The parallel postulate of Euclidean geometry is replaced with: :For any given line ''R'' and point ''P'' ...

) 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 of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of ...

NP, but it is not known to be

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...

, nor is it known to be solvable in

polynomial time In 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 performed by ...

. Yet, Fordham's algorithm computes rotation distance in linear time, but only allows rotations on the root node and its right child. Fordham's algorithm relies on a classification of nodes into 7 types, and a lookup table is used to find the number of rotations required to transform a node of one type into another. 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 solu ...

for the problem with an

approximation ratio An approximation is anything that is intentionally similar but not exactly equal to something else. Etymology and usage The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix ' ...

of two. A similar approach of partitioning into subproblems along shared diagonals leads to a

fixed-parameter tractable In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...

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 In 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 performed by ...

. Yet, the existence of Fordham's algorithm strongly suggests a linear time algorithm exists for computing rotation distance.

References

{{reflist, refs= {{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 reviewed scientific journal in the field of computer science, published by Elsevier Elsevier () is a Dutch academic publishing company specializing in scientific, technical, and medical content. Its ...

, 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 The ''Journal of Graph Algorithms and Applications'' is an open access peer-reviewed scientific journal covering the subject of graph algorithms and graph drawing. The journal was established in 1997 and the editor-in-chief is Giuseppe Liotta (Univ ...

, mr = 2740180 , pages = 385–390 , title = A linear-time approximation for rotation distance , volume = 14 , year = 2010, doi-access = free {{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 , last1 = Kanj , first1 = Iyad , last2 = Sedgwick , first2 = Eric , last3 = Xia , first3 = Ge , doi = 10.1007/s00454-017-9867-x , issue = 2 , 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 geom ...

, mr = 3679938 , pages = 313–344 , title = Computing the flip distance between triangulations , volume = 58 , year = 2017, arxiv = 1407.1525 , s2cid = 1961246 {{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 , 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 {{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 abstr ...

, 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