It’s Triangles All the Way Down (Part 2)
Diego Hernandez, Griffin Koontz, Amy Liu
In Part 1 of this post, we explained the isometry between binary trees and polygon triangulations, as advanced by Sleator, Tarjan, and Thurston. In this part, we’ll be exploring some new uses for this isometry that provide interesting insights into binary search trees, multiway trees, and more. If you haven’t read Part 1, we recommend first reading the section The Isometry Between Binary Trees and Polygon Triangulations.
Exposed triangles
One notion we will need in the following discussion is that of an exposed triangle. Let’s define an exposed triangle in a triangulation to be a triangle where at least two of its three sides are edges of the original polygon (all three sides of an exposed triangle fulfill this property only in the case of a binary tree with a single node).
One property of exposed triangles is that they correspond to leaf nodes, or in some cases the root node, in the corresponding tree. To understand why, consider how a shared edge between two triangles in the triangulation denotes an edge between two nodes in the binary tree. Because exposed triangles share at most one edge with another triangle, the corresponding node of an exposed triangle can be connected to at most one other node. Thus, the node can either be a leaf node or a root node with only one child. If the tree consists of a single node, the node has no parent or children, and all three edges of the corresponding triangle are exposed.
Binary search tree operations
Insertion into a binary search tree amounts to making a new leaf in the appropriate place; i.e., introducing a new parent-child relationship. In the triangulation, we need to make a new vertex between its inorder predecessor and successor. This is illustrated below with the insertion of the node 3.
Note that we don’t need to change any of the pre-existing diagonals, since the shape of the rest of the tree remains the same. And the two newly-added edges of the polygon create a new exposed triangle that shares an edge with its parent triangle.
Deletion from a BST is a more complicated operation: it is commonly considered in three cases based on the number of children the node to delete has. Surprisingly, it turns out that the corresponding operation in the BST’s triangulation is the same across all three cases. Let’s take a closer look at each case.
Case 1: If the node has no children, just remove it.
In the triangulation, this just amounts to removing an exposed triangle. Another way to think about it is to have the successor vertex move toward the node to delete until it “swallows” the node to delete. This is illustrated below, with the 2 vertex moving to “swallow” the 1 vertex.
Case 2: If the node has just one child, remove it and replace it with its child.
Since the node to delete has a child, its corresponding triangle may not be an exposed triangle. However, just as with Case 1, we can think of this deletion as moving the successor vertex until it swallows the vertex to delete.
Intuitively, this subsuming process amounts to having your successor take your place in the tree. You can also think of this as relabeling the triangle you’re deleting with its successor and shrinking away the old successor triangle.
Case 3: If the node has two children, find its inorder successor (which has zero or one child), replace node’s key with its successor’s key, then delete its successor.
Although this case is the most complicated of the three in terms of the tree representation, the turns out that in the triangulation, we can apply the same procedure used in the previous two cases. That is, take the successor vertex and move it so that it swallows the vertex to delete. This is illustrated below.
Generalization to multiway search trees
In this section, we generalize the binary tree/triangulation isometry to multiway trees. Whereas the triangulation for a binary tree is constructed by making a polygon vertex for each node of the tree, the polygon decomposition for a multiway tree is constructed by making a polygon vertex for each key stored in the multiway tree. As before, each polygon in the decomposition corresponds to a single node of the tree, but the departure is that the polygons need not be triangles. Instead of simply creating a root triangle from the root edge and its corresponding vertex, we make a polygon from the root edge and all the vertices corresponding to keys within the root node. This construction preserves the fundamental property that two shapes corresponding to adjacent nodes are adjacent in the polygon decomposition.
We also generalize our notion of exposed triangle to that of an exposed polygon. An exposed k-gon is a k-gon in a polygon decomposition, at least k−1 of whose sides are also edges of the overall polygon.
2–3–4 trees
Having generalized the tree/triangulation isometry to multiway trees, we now examine 2–3–4 trees, a particular kind of multiway tree. Below we present the rules for 2–3–4 trees, accompanied by the rules for their corresponding polygon decompositions.
An example 2–3–4 tree and its corresponding polygon decomposition are drawn below.
We now examine insertion into a 2–3–4 tree. With the tree, the first step is to add the new key to the appropriate leaf node. With the polygon decomposition, this corresponds to adding a new vertex in the appropriate place, similar to BST insertion. But instead of creating a new exposed triangle, we add a new vertex into one of the constituent polygons. This is illustrated below with the addition of the key 5.
The next step is to recursively split the node if it becomes too large. This occurs when the node has 4 keys, i.e., when its polygon is a hexagon. Splitting this 4-key node therefore corresponds to splitting a hexagon into a quadrilateral and triangle, with a middle triangle left over. The leftover triangle is then recursively added to the parent polygon (which may itself need to split, and so on).
We now examine deletion from a 2–3–4 tree. Deletion is tricky because if we delete a key that is the only key in its node (thereby deleting an entire leaf node), we would violate the rule that all root-null paths must pass through the same number of nodes. So, if the key we want to delete is the only key in its node, we must first perform a transformation on the tree to boost the number of keys in that node. In the polygon decomposition for the 2–3–4 tree, there’s a nice geometric analogue for this. Specifically, if we are about to remove an exposed triangle, that exposed triangle needs to steal vertices from nearby polygons. Let’s go through the three cases for deletion in more specific terms.
Case 1: Node has at least two keys.
Tree: Just delete the key.
Polygon: Just delete the vertex and replace the missing two edges with a single edge.
Case 2: Node has only one key, but sibling has at least two keys.
Tree: Steal from parent, parent steals from sibling. Then delete the key.
Polygon: “Triangle shift” operation; a single vertex of the parent polygon shifts to give a vertex to the polygon of interest while taking a vertex away from a sibling polygon. Then delete the desired vertex.
In the illustration below, the triangle for the node 2 shifts to become a triangle for the node 3, thereby giving the 2 vertex to the 1 triangle.
Case 3: Both node and sibling have only 1 key.
Tree: Steal from parent and fuse node with its sibling. Recursively delete the stolen key from that parent node.
Polygon: “Triangle reduction” operation; replace two consecutive edges in the parent polygon with a single edge. This combines two exposed triangles, resulting in an exposed pentagon. Then delete the desired vertex.
Note that if the parent polygon is a triangle, a “triangle reduction” operation reduces the parent polygon to a line segment. In this way, the grandparent polygon automatically becomes the new parent; we then recursively delete from this new parent to put a new triangle between it and the original polygon, as per the equal-leaf-depths rule for 2–3–4 trees.
Connection to the red-black tree/2–3–4 tree isometry
We note that the isometry between red-black trees and 2–3–4 trees can be easily visualized via triangulation/polygon decomposition. Since a red-black tree can be turned into a 2–3–4 tree by contracting all red nodes into their parent black nodes, a triangulation for a red-black tree can be turned into a polygon decomposition for its corresponding 2–3–4 tree by fusing all red triangles with their parent black triangles.
Split and join
Using polygon decompositions, we can also visualize tree splits and joins in a new way. In this section we provide a rough sketch of what that would look like.
To join two 2–3–4 trees, we add the joining key to the taller tree (recursively splitting nodes and propagating a key upwards as necessary) and then make the smaller tree a child of the joining key. In the polygon decomposition this amounts to adding a new vertex to some polygon in the decomposition for the taller tree (recursively splitting hexagons and propagating a triangle upwards as necessary, as described above), which adds an exposed edge to that polygon. Then attach the root edge of the polygon decomposition for the shorter tree to that new exposed edge.
Splitting a red-black tree at a node involves cutting all tree edges on the access path from the root to the inorder successor of the node. Since successive edges in this access path have one endpoint in common, and an edge in a tree is represented by an edge between two triangles in a triangulation, it can be seen that cutting the desired edges in the tree amounts to cutting the polygon along a path in the triangulation.
Conclusion
In this part of our writeup, we built on Sleator, Tarjan, and Thurston’s isometry between binary trees and triangulated polygons and explored how binary and multi-way search tree operations manifest in polygon world, sometimes with surprising simplicity as with BST deletions. It’s also interesting to study the split and join operations, which correspond to literally splitting and joining polygons. Furthermore, the isometry scales effectively to multi-way trees; instead of triangulation, polygons corresponding to multi-way trees are subdivided into smaller polygons. That said, it’s also important to acknowledge the limitations of the polygon representation. Many binary tree operations that we explored, such as splaying, did not have meaningful geometric representations; we chose to exclude them from this writeup.
More broadly, the parallel between binary trees and triangulated polygons speaks to the effectiveness of using isometries to analyze data structures. Calculating rotation distance between two binary trees is a sophisticated problem in itself; indeed, whether rotation distance for two particular trees can be computed in polynomial time is still an open problem in computer science. But when we consider a binary tree through the lens of the polygon isometry, the upper bound on rotation distance becomes easier to understand. Using isometries is a fun and beneficial way to explore data structures, and we hope this discussion leaves you with a greater appreciation for the modest binary tree.
Resources + References
We put together some slides to go along with this writeup:
In addition, we built an interactive tool that allows you to see binary trees side by side with their corresponding triangulations:
Sleator, Daniel D., Robert E. Tarjan, and William P. Thurston. “Rotation distance, triangulations, and hyperbolic geometry.” Journal of the American Mathematical Society 1.3 (1988): 647–681.
A huge thanks to Keith Schwarz and the Spring 2018 CS166 course staff for project feedback, numerous whiteboard conversations, and telling us about the original Sleator, Tarjan, and Thurston paper.
