In discrete mathematics and theoretical computer science, the rotation distance between two binary trees with the same number of nodes is the minimum number of tree rotations 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 polygons. Rotation distance was first defined by Karel Čulík II and Derick Wood in 1982. Every two n-node binary trees have a rotation distance of at most 2n − 6 for all n ≥ 11, and some pairs of trees have exactly this distance. The computational complexity of computing the rotation distance is unknown.
Definition
A binary tree 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 x in the tree, there is a subtree of the same form, rooted at x and consisting of all the nodes that can reach x 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, 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 tree rotation is an operation that changes the structure of a binary tree without changing its left-to-right ordering. Several self-balancing binary search tree data structures use these rotations as a primitive operation in their rebalancing algorithms. A rotation operates on two nodes x and y, where x is the parent of y, and restructures the tree by making y be the parent of x and taking the place of x in the tree. To free up one of the child links of y and make room to link x as a child of y, this operation may also need to move one of the children of y to become a child of x. There are two variations of this operation, a right rotation in which y begins as the left child of x and x ends as the right child of y, and a left rotation in which y begins as the right child of x and x ends as the left child of y. 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, triangulations of polygons, and triangulations of abstract manifolds. There is a one-to-one correspondence between triangulations of a given convex polygon, with a designated root edge, and binary trees, taking triangulations of n-sided polygons into binary trees with n − 2 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 (n − 2)-node trees corresponds exactly to flip distance on triangulations of n-sided convex polygons.
… excerpt ends here. Continue reading the full article.
