Seriously, this again?
As you can tell from the title of this post, I will be making no allusion to the originality of this topic or its necessity. However, anyone who has studied data structures understands both the versatility and importance of trees. Further, anyone who has studied time complexities in regards to operations (searching, inserting, etc.) on trees also knows the importance of keeping a tree balanced. To balance (most) trees one employs rotations on sub trees where the imbalance is rooted. These rotations help keep the tree (roughly) balanced thus guaranteeing certain time complexities.
So far I’ve defended the existence of this post with a few overly wordy sentences, and a weak defense it has been. Why then am I writing about something as simple as tree rotations? Its all about generalization.
Generalization breaks down complication
I remember studying binary search trees during my undergrad and getting frustrated with the heavy use of recursion. The algorithms I studied used recursion for searching, inserting, deleting, and in some cases for “fixing” specialized tree structures (think red-black trees). While at that time I understood how recursion worked, I was not convinced it was necessary. It had until that point seemed as if recursion was a tool used solely in pissing matches in an effort to make algorithms more complicated than they need to be. Surely a loop could do just as good of a job as a recursive function all the while making the algorithm easier to read and understand.
Then, little by little, recursive algorithms would emerge from almost nothing at all simply by generalizing the problem and programming “in the small”. By generalizing appropriately I could develop simple and concise algorithms that were easy to read and understand. Thankfully I realized this prior to studying functional programming, whew.
I think all CS undergrads experience the same frustrations I had in regards to trees and recursion. However, I don’t think all CS undergrads draw the conclusion that generalization is the key to understanding why recursion is so damn useful and beautiful. Thankfully the usefulness of generalization has a surface area larger than that of just recursion, otherwise I would have to generalize generalization. And from there, its turtles all the way down.
A tree of trees
You might already know that tree rotations do not require recursion and are rarely seen implemented with recursion. If you come across a rotation algorithm that does, tread carefully (I suppose you could develop a recursive double rotation function, but I’ll leave it up to you to determine why that may not be your best option). I only used recursion in my example above because in my opinion recursion can be the most beautiful realization of the process of generalization.
Nowadays I’m a generalizing fool. It can sometimes be difficult to express the usefulness in such an abstract concept. But anyone familiar with object oriented programming understands this concept and its usefulness quite well.
For the past couple weeks I would use some of my free time to develop a red-black tree implementation (which I will share soon). For those of you not familiar, a red-black tree is a specialized self-balancing binary search tree which exhibits seemingly random ways to balance itself. Of course there is nothing random about the way it balances itself, but it does take some getting used to and that’s a discussion for another day.
Like several other self-balancing trees, the red-black tree uses tree rotations to align the structure of the tree with its definition. Tree rotations are not very complex, but I couldn’t help but admire the ease in which they can be programmed and understood when the tree is generalized appropriately. The generalization I find appropriate is to think of any given node in the tree as a root node of a sub tree, a tree of trees if you will. I know that may sound obvious, but this is not intended to be some sort of watershed event. I’m merely appreciating how generalization can make working with a tree easier.
Lets generalize
There are two flavors of tree rotations; left and right:
Thanks to Wikipedia for the above picture. Starting from the left, Q acts as the root node and P acts as the pivot node. When the tree is rotated right, the pivot becomes the root and the previous root becomes the new root’s right child. You can see how something similar happens when performing a left rotation. We will further generalize this concept, but let’s first code a right rotation in C#.
public void RotateRight(Node Root, Node Pivot)
{
Root.Left = Pivot.Right;
Pivot.Right = Root;
}
Where a Node is defined as:
public class Node
{
public int Value { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
}
You can see the rotation is quite simple; but there is a problem. What would happen if the Root node used was not the root of the entire tree, but rather that of a sub tree. If that were the case the parent of our Root node Q would know nothing of the rotation and you would end up with something like this:
Uh oh, we’ve orphaned the sub tree rooted at P! Thankfully this is easy to remedy. After the rotation, we could assign our pivot node as the root of the sub tree, using the ref modifier to make sure any references further up the tree are also updated:
public void RotateRight(ref Node Root, Node Pivot)
{
Root.Left = Pivot.Right;
Pivot.Right = Root;
Root = Pivot;
}
Oh joy. But you know something? I’ve never been a fan of the ref modifier. It has a knack to make the call site difficult to reason about. Not to mention it has the potential to cause a far reaching side effect. But perhaps my biggest issue is that in this case the code does not adequately illustrate the reason for the Root assignment and its reliance on the ref modifier. We can do better. Ignore the fact that we may have a larger tree structure than is visible during rotation. We’re going to generalize how the rotation works without regards to what may or may not exist higher up in the tree. In a sense, we’re going to pretend our sub tree is the entire tree. Then all that’s left is to determine how to handle the case that our tree has a new root node. The easy thing to do would be to return the new root:
public Node RotateRight(Node Root, Node Pivot)
{
Root.Left = Pivot.Right;
Pivot.Right = Root;
return Pivot;
}
The call site can do whatever it wants with the new root of the sub tree, such as assigning it to the root of the entire tree or fixing a child reference. From the perspective of the rotation, it doesn’t matter what happens to the new root. By generalizing the concept of a rotation to be unaware of the overall structure of the tree, our rotation algorithm is very easy to reason about.
But we can make this even better. Notice how the pivot node is always the node opposite the direction of the rotation? With that knowledge we can determine the pivot node on our own:
public Node RotateRight(Node Root)
{
Node pivot = Root.Left;
Root.Left = pivot.Right;
pivot.Right = Root;
return pivot;
}
public Node RotateLeft(Node Root)
{
Node pivot = Root.Right;
Root.Right = pivot.Left;
pivot.Left = Root;
return pivot;
}
Notice I also included the code for a left rotation. While that may not look like we made any sort of benefit by determining the pivot node on our own, we’ve actually opened the door to our next generalization. Let’s make some observations first:
- The pivot node is the node opposite the rotation direction.
- The child of the root node opposite the rotation direction becomes the child of the pivot node in the direction of the rotation.
- The child of the pivot node in the direction of the rotation becomes the root node.
- The pivot node is the root of the tree.
I know #2 got a little wordy, but I could not manage to trim any fat off that sentence. After you absorb those observations and think about how to generalize them, you may start to realize that we might be able to combine the left and right rotation functions by being given the direction of the rotation and then determining the opposite direction on our own. In fact, that’s exactly what we’ll do. Let’s first start by redefining our node class to accommodate being able to return a child given a direction:
private class Node
{
public enum Direction
{
Left = 0,
Right = 1
}
public int Value { get; set; }
private Node[] _children;
public Node this[Direction Child]
{
get
{
return _children[(int)Child];
}
set
{
_children[(int)Child] = value;
}
}
public Node()
{
this._children = new Node[2];
}
public static Direction Opposite(Direction Path)
{
if (Path == Direction.Left)
{
return Direction.Right;
}
else
{
return Direction.Left;
}
}
}
I know that adds a bit of complexity to the definition of a Node, but interacting with its children is still quite easy, as you’ll soon see. You’ll often find tree structures implementing parent-child relationships with individual child pointers or references, as was done previously. In this case, I use an array to store child references. Index 0 represents the left child, and index 1 represents the right child, as shown by the values of Left and Right in the Direction enumeration. An indexer is then used to interact with a specific child just by specifying a value from the Direction enumeration. This provides me with a concise and consistent method for interacting with the children of a node. Note that an indexer would not be necessary if C# allowed for implicit conversions between values in an enumeration and the underlying type (integer in this case) of the enumeration.
Using our observations above, we can easily develop a direction agnostic rotate algorithm. What you’ll see is this algorithm has striking parallels to the direction specific ones, but is the result of generalizing what the direction does to the tree:
public Node Rotate(Node Root, Node.Direction RotationDirection)
{
Node.Direction oppositeDirection = Node.Opposite(RotationDirection);
Node pivot = Root[oppositeDirection];
Root[oppositeDirection] = pivot[RotationDirection];
pivot[RotationDirection] = Root;
return pivot;
}
Boom goes the dynamite
As previously noted, nothing in this post is ground breaking or heart stopping. In fact, you may have found this post downright boring. But that’s OK. I intended to illustrate my love of generality with proof that it can be a beautiful thing, which I think came to fruition.
