The Diagonal-flip Of Convex Polygon Triangulations And The Rotation Of Binary Trees

The diagonal-flip (rotation) of triangulations (binary trees) can achieve the conversion between two triangulations (binary trees). The diagonal-flip (rotation) distance between two triangulations (binary trees) is the minimum number of diagonal-flip transformations (rotations) needed to convert one triangulation (tree) into the other. There exists a well-known explicit bijection between binary trees and convex polygon triangulations, thus the diagonal-flip distance of convex polygon triangulations and the rotation distance of binary trees are equivalent. Therefore, we can study the rotation distance of binary trees from the perspective of triangulations.The binary tree is a frequently used data structure in the algorithm design and analysis. In the binary tree algorithm analysis, the average performance of binary trees with some features is often needed to be discussed, so the binary tree enumeration is needed to be realized. Thus, the problem of enumerating binary trees is of great interest both theoretically and practically.In this paper, firstly, three special types of triangulations for the convex polygon are studied, the diagonal-flip distance of them is obtained, and the algorithms are given to compute the diagonal-flip distance between them. Then, according to the well-known explicit bijection between triangulations and binary trees, the rotation distance of binary trees is obtained.Secondly, two binary tree enumeration algorithms are proposed. One is by enumerating convex polygon triangulations to achieve under the one-to-one relationship between binary trees and triangulations. The other is through a special binary tree rotation (left arm right rotation) to achieve.Finally, key work done in the paper is summarized and the future work is given.