Every semester, without fail, I get dozens of questions about tree rotations. It gets confusing to keep track of the direction of the rotation and the steps to reorganize the tree afterwards. It doesn't help that we don't spend too much time covering it in class either. This post seeks to make understanding tree rotations, their uses, and their algorithms just a little bit easier!
This post assumes familiarity with Binary Search Trees [1] [2] [3] and AVL constraints [4] [5]. If you're unfamiliar with either, then I recommend brushing up on those concepts before jumping into tree rotations. Before we start, it's important to note that tree rotations happen sparingly, and you'd only perform a rotation if a subtree is unbalanced. Otherwise, if your tree is balanced, there's no reason to do a tree rotation, and doing so might actually cause more problems. With that out of the way, let's get started!
Let's start with a Binary Search Tree. Since tree rotations are a way to balance our search tree, we'll make sure that our binary search tree is unbalanced. Since there are different ways to balance search trees [6], our goal will be for our tree to adhere to AVL balance constraints. Let's look at the example below:
Figure 1: A balanced AVL BST.
Let's say we remove Node F. Now our tree looks like this:
Figure 2: Our tree from Figure 1, with Node F removed.
Since this is an AVL tree, the balance factor of Node F's ancestors has changed, which causes Node C to have a balance factor of +2. Before removing Node F, Node C had a balance factor of +1. We'll have to rebalance our tree in order for it to adhere to AVL constraints. This is where tree rotations come in!
Our Special Rotation Algorithm:
We'll need to rotate Node F's parent, Node C, the node with the +2 balance factor, over to the left.
Figure 3: Our tree from Figure 2, but now we're preparing for a left rotation around Node C.
A leftward rotation will allow for Node C's right child, Node G, to become the parent of that entire subtree, while Node C becomes the new left child of Node G [7]. Node H becomes the right child of Node C. This preserves the ordering of the BST, since we want to make sure we maintain those constraints as well (a value smaller than the parent goes to the left, while a value bigger than the parent goes to the right).
Figure 4: Our new AVL tree after rotating around Node C.
Note that Node I doesn't change its position ever, it just stays put relative to the rotation. The Node G's former left node, Node H does change; it becomes the right child of Node G's "new" left node. If Node H were to have subtrees, those subtrees would not need to be changed.
Note that our new balance factor for Node G is -1 and Node C is +1. These are now within an acceptable range for our AVL tree constraints.
Final Algorithm:
Now that we know the steps we need to take, let's write down our algorithm in a cleaner way.
Since we just performed a left rotation, we can now infer the steps for a right rotation. Let's start with a slightly different AVL Tree (which, with the correct values, could also be a heap! [8]).
Figure 5: A brand new AVL tree, oOoOoOo...
Let's pretend we removed Node E. This would change our balance factor for Node B to -2 [9]. In order to fix this, we would need to do a rightward rotation around Node B. After doing so, Node B's balance factor will be 0, with Node D's balance factor becoming +1.
That's all there is to it! I recommend practicing drawing your own tree with different balance factors, then removing or adding a node, and trying to use a rotation to balance your tree. It's good practice that will help you visualize the process. Until next time!
Sources & Side Notes:
[1] Stanford's BST Lecture Slides.
[2] CMU's BST Notes.
[3] UB's BST Lecture Slides.
[4] Stanford's AVL Lecture Slides.
[5] AVL Tree Visualizer.
[6] AVL vs. Red Black Trees.
[7] UB's Tree Rotation Lecture Slides.
[8] Algosaurus - Heaps, Please note that you shouldn't do tree rotations on heaps, they'll break the structure of a heap. Please.
[9] Removing Node E doesn't affect Node A's balance factor because the height of its children never changes.
