AVL Trees & Where To Find (Rotate) Them
Hello, folks! Welcome to AVL Trees (simplified, and named after inventors Adelson-Velsky and Landis). Today, we will be walking through the logic and my own Javascript implementation of inserting a value into a binary search tree (BST), and then utilizing the stricter AVL tree rules to balance the tree if necessary.
Now … what does that mean?
When I first learned about BSTs, I was very excited to make my own, and was severely disappointed when I learned that it was possible for a BST to be completely useless (‘degenerate’) when the inputs are sorted. The ideal position for a tree is to have a root that has equal left halves and right halves to minimize lookup, insertion, and deletion times.
So, I figured I (kind of) get the concept, I’ve made a (basic) tree, I (sort of) like these changing pointers … why not try it out for myself?
Now, forewarning, there exists several methods to balance a binary search tree, and the following is my interpretation to transform concept to code. The helper functions that I’ve created here are not conventional.
AVL Tree Magic
AVL trees are one of many types of height-balanced binary search trees, where we go from this:
to this:
Two different properties will be added to my BST constructor: a link to the parent node, and a height method. The height of a tree is the longest path from root node to any leaf node. In this post, we will be working exclusively with inserting nodes, and rotating nodes when the AVL rules are violated.
AVL Rules
1. A tree is height-balanced when the heights of its child trees differ by at most 1.
2. The balance factor is defined as an integer in the range of [-1, 1] where -1 will be an extra node on the right child tree, and 1 is an extra node on the left child tree, accounting for an odd number of nodes.
3. A tree is considered unbalanced when the balance factor falls outside that range, and nodes undergo rotations to rebalance the tree. There are 4 different categories of rotations: left-left, left-right, right-right, and right-left.
4. The resulting height of the tree is then log2(n), which will make traversal time O(log2(n)).
Now, looking at those rules, you might be wondering: why do I care? Why go through all of this extra effort just to make a tree look more like its namesake?
With smaller data sets, the lookup time for a regular tree and a balanced tree is similar, but when your data sets become thousands of nodes deep, or even tens of thousands, suddenly the range of possibility is at best O(lg n) and at worst O(n), or that of traversing a linked list. With a balanced BST, you can always guarantee O(lg n) lookup time in both average and worst-case scenarios. I like guarantees.
The Visual Logic
Let’s take a look at the initial example of creating a BST of 20 as its root (Step 1), and then inserting the following: [15, 25, 10, 7]
The rules for a BST are as follows: if the value is less than or equal to the root move to the left, else move to the right.
The first insertion (Step 2) will place 15 to the left of 20.
These second insertion (Step 3) will place 25 to the right of 20.
The third insertion (Step 4) places 10 to the left of 15.
The fourth insertion (Step 5) places 7 to the left of 10.
Step 5 has now violated the rule of an AVL tree. The resulting situation forces nodes to rotate. When the root node (15) is unbalanced, and its left side is longer than the other. The rotation will come from the side that is longer — the left side. The root’s left node (10) is known as the ‘pivot’ node. This node will determine whether the rotation will be right or left depending on whether it has a balance factor of 1. If it has a balance factor of 1, then the left side is longer than the right, and this situation is known as a left-left, for the left node as a pivot, and the longer left side, which will force a right rotation. The root node will move to the pivot node’s right side, and the pivot node will be directly attached to the rest of the tree. If the pivot node had a right side, it will move to the root node’s left.
The same situation but mirrored is known as a right-right, causing a left rotation.
The other 2 scenarios are left-right and right-left. There will be 2 resulting rotations instead of 1, as explained below:
The opposite situation is if 14 were placed instead of 7 in Step 5.
Now the ‘pivot’ node has a balance factor of -1, which is going to cause a left rotation using the pivot node as the root node, and its right node as the pivot. Once that is complete, the second rotation is a right rotation with the original root node and the new pivot node. Both of these rotations have already been defined above. The mirrored situation results in the right-left rotations.
These are the general rules of an AVL tree in particular. There are many other methods to a height-balanced tree, and even algorithms to optimize the height of the tree over a given amount of time.
Now let’s dive into Javascript.
Code Base Logic:
To determine the height of a tree, a recursive function defined as BinarySearchTree.prototype.height returns -1 if the root is null, and otherwise sums the maximum of the tree’s left and right sub-tree heights + 1. The code is defined below:
With the height method available, I can then determine the balance factor of each of my successive parent nodes after the insertion of a leaf node as the difference of the two, defined as BinarySearchTree.prototype.balanceFactor:
Part 1: Insertion of a leaf node:
The code block of the insert prototype method takes the new value, and performs a recursive call until it hits a node with no corresponding right/left. After inserting the node, it performs this function on the node, now aliased as root:
Walking through this: if the root’s balance factor is outside of the balance range, it will need to be rotated. Otherwise, until the root no longer exists, this function will recursively check the parent node.
Part 2: Establishing the rotation process:
The idea here is that the nodes will either move left or right (imagine a 45 degree diagonal plane for this) depending on the status of its balanceFactor. The 4 rotations take into account the possible positions of unbalanced situations: the first two consider whether the unbalanced situation has extra nodes on the left or right side, and then consider the same situation for the designated pivot node.
Note that because the balanceFactor is >0 or <0, there is automatically going to be a child node on either side, so there is no need to verify if there exists a left or right root.
Part 3: Rotating nodes:
Now that we have been able to establish the direction of the rotation, we can perform the rotation itself. I have generated an example of a rightRotate method to be clear, but since there exists a mirrored method for leftRotate, I also have implemented a generalized method rotateChoice that accounts for both situations. Today, we will walk through the rightRotate method for clarity.
Here, we need to understand that a BST has the following in its constructor:
And note that the BST rotation requires a pivot node in addition to the root node from the first portion of our talk.
Let’s walk through the workflow.
We are on Step 5 of inserting into the tree, and we have hit our first unbalanced scenario: we’ve inserted 7 into the tree, but now our tree’s balanceFactor is out of range. As we perform checkAndRotateRoots up the tree from the leaf node, we find the following:
7 has a height balance of 0, 10 has a height balance of 1, and 15 has a height balance of 2, breaking the rule on the left side.
So on 15, we will need to perform rotate.
Now, we have to check the pivot node, which is the tree on 15’s left (10), whose height balance indicates an extra node on the left side. This results in 1 rotation: a left-left situation results in a right rotation on the root, as per our diagram.
Now comes the fun part: rotation and re-assignment! Here is what that particular branch looks like, individual node-wise:
As we can see, there are several links between each node that we have to be careful of when disconnecting and reconnecting links.
In order to perform a right rotation, the root node (15) will move to the right, and its pivot node (10) will take its place. This will re-establish the following:
The pivot node’s parent is now going to be the parent node (20), and the parent node’s new left is going to be the old pivot node. The pivot node’s right will be the old root node, and the old root node’s parent will be the pivot node, or new root node. The old root node’s left will now be null. If the new root node initially had a right child, that would have become the old root node’s left. This takes care of all of the relationships included.
This is as seen below:
The same will apply for a left rotation. For left-right and right-left rotations, each of the 2 rotations apply the same logic.
For this particular scenario, a BST is defined with a root value. This current application will rotate the tree, and the diagram of the tree will be rendered as such. However, should the tree need to rotate its root node, the tree itself will remain the same, except that the root node will now be off-center. There are other ways to approach creating a BST where we start with an empty tree, and insert values with a pointer to the root node.
Thank you, and please let me know if you have any questions!
Sarah
Sources:
- Introduction to Algorithms 3rd Edition by Cormen, Leiserson, Riverst, & Stein
- CS241 — Lecture Notes: Self-Balancing Binary Search Tree: [https://www.cpp.edu/~ftang/courses/CS241/notes/self%20balance%20bst.htm]