It’s Triangles All the Way Down (Part 1)
How can polygon triangulations shape our understanding of binary trees?
Diego Hernandez, Griffin Koontz, Amy Liu
Introduction
Binary trees are a wonderfully common data structure in computer science; their simplicity, versatility, and quick runtime guarantees make them a great choice for many applications. We usually represent binary trees, both conceptually and in code, as graphs — nodes connected by edges — with a particular node designated as the root. To store data in a binary tree, we store a value, known as a key, in each of the nodes.
However, this isn’t the only way we can visualize binary trees. In a 1988 paper entitled Rotation Distance, Triangulation, and Hyperbolic Geometry, Daniel Sleator, Robert Tarjan, and William Thurston introduced a way to represent any binary tree as a polygon triangulation (we’ll explain this soon). They then used this isometry to prove that the rotation distance between any two binary trees of m nodes is at most 2m−6.
More than merely proving this upper bound, this isometry between binary trees and triangulations allows us to think about trees in a new way. In this first part, we will explain this isometry as well as the proof of the 2m−6 upper bound on rotation distance, as advanced in Sleator, Tarjan, and Thurston’s paper. Then in Part 2 we’ll explore some interesting new applications of this isometry in binary search tree operations, multiway trees, and other areas.
The Isometry Between Binary Trees and Polygon Triangulations
How, you may ask, can we represent a binary tree with a polygon? The process involves triangulation, where we recursively divide the polygon into triangles. A triangle represents a node in the binary tree, and a shared edge between two triangles indicates that the two corresponding nodes in the tree are adjacent.
Importantly, the triangulation process only considers the tree’s shape rather than considering any keys that may be stored in the nodes. To illustrate this, we relabel each node with its place in the symmetric order (i.e., the order generated by an inorder traversal of the binary tree). Supposing you start with an m-node binary tree, relabel the nodes as follows:
Now, draw a convex (m+2)-gon. Designate an arbitrary edge to be the root edge, and label the remaining vertices of the polygon that are not on the root edge with the numbers one through m. As a convention, we’ll go counterclockwise.
Create a triangle by drawing line segments from the root edge’s endpoints to the vertex corresponding to the root node of the tree. We’ll refer to these segments as diagonals. This triangle, called the root triangle, represents the root node.
Notice that the root triangle separates the vertices corresponding to the left subtree (1 through 4, in the figure above) from the vertices corresponding to the right subtree (6 and 7). Drawing the root triangle, then, decomposes the polygon into (at most) three polygons: the root triangle itself, plus a polygon for each of the two subtrees of the root.
To complete the triangulation, recursively triangulate each of these two polygons according to the process described above, using the two newly-drawn diagonals as the root edges of their respective polygons. In the figure below, we start with the left subtree, connecting the new root edge in the leftmost polygon to the vertex (2) corresponding to the root node of the left subtree. Similarly, these diagonals act as root edges for the newly created polygons, which correspond to the subtrees of node 2. We repeat the same procedure to triangulate the entire left subtree; at this point we just need to draw one additional diagonal to complete the triangle that corresponds to node 3. Next, we follow the same procedure for the right subtree.
A binary tree has only one possible triangulation because each triangle in the triangulation is uniquely determined by two things: 1) a diagonal that has already been drawn as part of the triangulation (or the root edge as a special case) and 2) the vertex of the polygon corresponding to a particular node.
In addition, one convenient property of the isometry is that two triangles are adjacent (share an edge) if and only if their corresponding nodes in the tree are adjacent (have a parent-child relationship). This property will be useful later on.
To more clearly see which triangles correspond to which nodes, it may be helpful to overlay the tree on top of its triangulation, shown below. Notice how it’s still possible to discern the original tree structure when looking at its triangulation.
If you’d like to experiment with the triangulation yourself, we created an interactive demo here:
Tree rotations as diagonal flips
What effect does a rotation in a binary tree have on its triangulation? To answer this question, we will think of rotation as two separate steps: first, contract the child node up into its parent, and then expand the old parent down as a child.
Since nodes in the tree correspond to triangles in the triangulation, merging two nodes corresponds to fusing the corresponding two triangles together to create a quadrilateral. Then, to delineate the new parent-child relationship, we draw in the other diagonal (i.e., the diagonal of the resulting quadrilateral that is not the previous diagonal). This operation is known as a diagonal flip.
The 2m−6 Upper Bound
Sleator, Tarjan, and Thurston introduced and used the isometry above to prove that the rotation distance between two m-node binary trees is at most 2m−6 for sufficiently large m. In this section, we will explain their proof in detail (the less technically rigorous reader may wish to jump ahead to Part 2, where we use the isometry to give a new perspective and visual intuition for binary search trees, multiway trees, and more). Although not all of the techniques used in the proof are immediately relevant to the novel applications we advance in Part 2, the proof provides a useful glimpse into the conceptual power of the isometry.
Diagonal flips in a triangulated polygon give us a powerful new way to think about tree rotations. By upper-bounding the number of diagonal flips needed to transform a triangulation of an (m+2)-gon into another, we also upper-bound the rotation distance between the two corresponding m-node trees. Suppose we have two binary trees of m nodes, and let T₁ and T₂ be their corresponding triangulations of (m+2)-gons. For notational simplicity, let n = m + 2, so that T₁ and T₂ are both triangulations of n-gons.
One useful way to transform T₁ into T₂ is to first transform T₁ into a particular triangulation that’s easy to work with, and then to transform T₂ into that same triangulation. The desired transformation from T₁ to T₂ will therefore come from performing the first transformation on T₁ followed by the inverse of the second transformation. The combined number of flips between the two transformations is an upper bound for the minimum number of flips required to transform T₁ into T₂ — that is, an upper bound for the rotation distance between the corresponding trees.
The intermediate triangulation we will use is one in which all diagonals emanate from the same vertex. Let’s call this kind of triangulation a fan. Our approach, then, is to transform both T₁ and T₂ into a fan and count the total number of flips required to to so.
Since any triangulation of an n-gon has n–3 diagonals, a fan has n–3 diagonals emanating from a single vertex. Let’s pick an arbitrary vertex x of our polygon; our approach will be to turn both T₁ and T₂ into a fan at x. Is this possible, and if so, how could we keep track of the number of flips required to do so?
Before we answer this question, let’s introduce a new term. The degree of a vertex in a triangulation is the number of diagonals emanating from it. In order to obtain a fan at x, we need the degree of x to be n−3. Now suppose that we have a triangulation in which the degree of x is less than n−3. Let’s figure out how we can turn it into a fan.
Consider all the line segments in the triangulation that lie “opposite” x; that is, consider all the segments that a) are part of triangles that include x as a vertex, but b) don’t themselves have x as an endpoint. An example triangulation, with segments opposite x indicated in bold, is shown below.
We claim that out of all the segments opposite x, there must exist some segment that is a diagonal in the triangulation. To see why, assume the contrary — that is, that all the segments opposite x are not diagonals, but rather part of the boundary of the polygon. Then the segments opposite x, plus the two polygon edges emanating from x, would form the complete boundary of the polygon. All the diagonals enclosed by this boundary must have x as an endpoint, and there are fewer than n−3 such diagonals. But this is impossible since any triangulation of an n-gon uses n−3 diagonals.
Therefore, as long as the degree of x is less than n−3, there exists some diagonal we can flip to increase the degree of x by one. It follows that given any triangulation, there is some sequence of diagonal flips we can perform to transform it into a fan. (An example is illustrated below.)
Since every such flip increases the degree of x by one, the number of diagonal flips needed to obtain a fan at x is the desired degree of x (namely, n−3) minus the degree of x before any flips are performed. Let deg₁(x) and deg₂(x) denote the degree of x in T₁ and T₂, respectively. Then we can transform T₁ into a fan at x in n−3−deg₁(x) flips and T₂ into a fan at x in n−3−deg₂(x) flips. In total, then, we can transform T₁ into T₂ in 2n−6−(deg₁(x) + deg₂(x)) flips.
In order to find an upper bound for this quantity, we should find a lower bound for deg₁(x) + deg₂(x); that is, the combined degree of x between the two triangulations. We begin with the fact that there are a total of 2(n−3) = 2n−6 diagonals between the two triangulations. Each diagonal has two endpoints, making a total of 2(2n−6) = 4n−12 endpoints. Each of these endpoints must coincide with one of the n vertices of the polygon. Therefore, by the generalized pigeonhole principle, there must be some vertex v where deg₁(v) + deg₂(v) ≥ ⌈(4n−12) / n⌉ = ⌈4−12/n⌉.
Up until now, our approach has been to transform T₁ and T₂ into a fan at some arbitrarily chosen vertex x. In order to use our newly found lower bound for deg₁(x) + deg₂(x), let’s tighten our approach by turning T₁ and T₂ into a fan at the particular vertex v for which deg₁(v) + deg₂(v) ≥ ⌈4−12/n⌉.
We want this lower bound to be as tight (i.e., large) as possible. Since 4−12/n < 4, we can’t make ⌈4−12/n⌉ exceed 4. However, we can make it equal to 4 by supposing that n > 12. So, suppose n > 12. Then the quotient 12/n is strictly between 0 and 1, so that 3 < 4−12/n < 4. This guarantees that ⌈4−12/n⌉ = 4.
Therefore, whenever n ≥ 13, we can transform T₁ into T₂ in at most 2n−6−4 = 2n−10 flips. This implies that we can convert their corresponding trees into each other in at most 2(m + 2)−10 = 2m−6 rotations, as long as the trees have at least 13−2 = 11 nodes.
Understanding the contribution from the isometry
From the above, it is clear that the tree/triangulation isometry plays a crucial role in the proof of the 2m−6 bound. But what exactly does it allow us to do that we couldn’t easily do with just binary trees?
Suppose that we tried to reproduce the above proof, but without any knowledge of the tree-triangulation isometry. In such a scenario, we will have to choose a tree as our intermediate configuration, rather than the fan triangulation introduced above. One reasonable choice is a degenerate binary tree (linked list). It turns out that it takes at most m–1 rotations to transform any binary tree of m nodes into a degenerate tree. This implies an upper bound of 2m–2 on the rotation distance between two m-node binary trees — a weaker bound than 2m–6.
Using the tree/triangulation isometry allows us to use a well-chosen fan as our intermediate configuration and thereby push the bound lower than 2m–2. What happens if we choose not to use the isometry, but instead just use fans’ equivalents as trees? In other words, what does a fan look like as a tree?
It turns out that for any arbitrary fan, its corresponding tree could be a degenerate tree. This occurs if and only if all the diagonals emanate from one of the root edge’s endpoints.
The other case is that it is a diamond-shaped tree — that is, one in which the left subtree of the root has all its nodes in its right spine, and the right subtree of the root has all its nodes in its left spine. This occurs if and only if we have a fan at one of the numbered vertices, rather than an endpoint of the root edge.
Ignoring the polygon isometry led us to use a degenerate tree as our intermediate configuration — a configuration that conveniently fits into our usual representations of binary trees. However, through using the isometry we expand the pool of options from which to choose an intermediate configuration. And as the proof shows, it must always be the case that there is a fan that pushes the bound lower, to 2m–6.
The above discussion also provides insight into what the degree of a vertex in a triangulation — a crucial notion in the proof — translates to in its corresponding tree. Specifically, we derive the following rules:
- The degree of the vertex on the root edge closest to 1 is the number of nodes in the left spine of the tree minus one.
- The degree of the vertex on the root edge closest to m is the number of nodes in the right spine of the tree minus one.
- The degree of a numbered vertex is the number of nodes in the right spine of the left subtree of that node, plus the number of nodes in the left spine of the right subtree of that node.
We encourage you to verify these rules with the example tree and triangulation illustrated below.
It is clear that the degree of a vertex in a triangulation has a more complicated interpretation in its corresponding tree. The tree/triangulation isometry is powerful because it represents this complicated concept in a simple and visually clear manner that lends itself to geometric and combinatorial analysis.
Conclusion
In 1988, Daniel Sleator, Robert Tarjan, and William Thurston presented a striking isometry: any structure of binary tree has a unique representation as a triangulated polygon, from which the entire binary tree can be reconstructed. While the isometry takes a little time to get used to, it captures the underlying elegance of binary trees. We saw how tree rotations are analogous to diagonal flips, and we observed how to turn a triangulation into any other by constructing a sequence of diagonal flips. Finally, we proved using the fan configuration that a m-node binary tree is no more than 2m−6 rotations away from any other.
In Part 2 of this post, we will explore some interesting new uses for this isometry that will provide new insights into binary search trees, multiway trees, and more.
