The beauty that is an AVL Tree

Over the course of my growth in the field of Computer Science, I’ve been introduced to a lot of concepts that helped me build a deeper understanding of my work, and do a better job as a programmer. One such topic I always find that I can never spend enough time studying is data structures. It’s always nice to have a properly implemented data structure that results in a more efficient runtime of your application, but there has never been one that I preferred above all others. Primarily dealing with the principal methods — Search, Insertion, and Deletion, there have always been ones that are good in either one or two of those methods, and something else that is good in the other(s). That is until recently when I came upon AVL-trees.

What made me fall in love was the versatility of the structure that allows you to reach really efficient runtimes in the functionality I mentioned earlier. When used right, AVL-trees can be used to carry out complex calculations in a humble runtime of just O(log n). I’d like to use this article to prove what makes AVL-tree so powerful by breaking down its structure, how the insertion, search, and deletion are implemented, and what brings about such an optimized runtime.

As you can see, the difference is huge. And with that said, allow me to elaborate on how it’s possible to bring about that.

As mentioned earlier, AVL-trees are basically self-balancing binary trees, so let’s talk about the self-balancing part. To do this, I’m going to first create a normal binary tree. Imagine creating a tree using a list of numbers — 12, 18, 21, 24, 27, 31, in that exact order. The binary tree would look like the following —

That’s because there’s no convention being followed during insertion other than just that the inserted item should be the left child or right child, and here every inserted item is bigger than the last one forming a structure in which a runtime for look-up or deletion is O(n).

AVL trees on the other hand, are called self-balancing tree for this reason. During construction, the algorithm makes sure the height-difference between the left , and the right subtree is no more than 1, i.e. the balance factor should be within -1, 0, and +1. In the example above, the node 12, has a height difference of 5 between its subtrees which isn’t allowed by the convention AVL-trees follow. I’m going to create the corresponding AVL-tree for the list mentioned above step-by-step to explain how this balancing works.

Inserting 12 and 18 is done normally as there’s no adjustment required. I have included the height difference of each node above it, + means the right subtree is dominant, — means left, and the 12 node has +1 balance which means it’s within the limit. After inserting 21, the height of the 18 node is still in the limit, but the height of the 12 node now is +2, which means it’s right subtree is heavier, and the tree needs to do a balance adjustment. Now if you look at the second tree in Fig. 2, we have 18 as the median, so if we just change the orientation of the tree such that 18 is the root with 12 as the left child and 21 as the right, balance is restored —

Now what’s the algorithm that caused this adjustment? To understand that, we need to move onto our next topic — rotations.

As you can see from the gif, there are two different forms of rotation: left and right rotations. What we did above was a left rotation. The triangles represent subtrees that are balanced, and are used to simplify instead of having to draw the whole subtree. In our above example, think of 12 as A, 18 as B, and 21 as γ(obviously α, β don’t exist in this example). Because 18 is what caused the imbalance in 12, that’s the pivot whereupon the rotation occurs(refer to both Fig. 2 and the gif to properly follow). 18 passes it’s left child(which is empty in the case of my example, but would’ve been bigger than 12 if it existed) to become the right child of 12, and then 18(which was the right child of 12 before) now becomes the parent, making 12 it’s left child. I hope you can see how rotations work(might be a good idea to take a screenshot of the gif when A is the parent, and follow the explanation).

The tree in Fig.1, after height adjustments, is shown as follows—

Now let’s consider a different scenario —

This is similar to the tree in Fig. 2 except that I passed in 14 after 18 instead of 21. 14 is the left child of 18, whereas 21 was the right, and so let’s make 18 a pivot, and perform a left rotation just like last time. The rotation resulted in 18 being the parent, making 12 the left child, and 18’s original left child, 14, would become 12’s right child(refer to the gif again, 14 is now β) and the result is another unbalanced tree —

Why does this occur? If you look at the balance factors, the signs are opposite, causing this behaviour. This calls for a different form of rotation called double rotation, i.e. it needs two rotations. First there has to be a rotation on the node that causes the unbalance with one of it’s children as the pivots, and then another rotation making itself the pivot. So let’s try this on the tree in Fig. 6. 12 causes the unbalance, but the balance factor of 12 also has the opposite sign to the node that it causes to become unbalanced(18), so we choose the child along which a rotation would match it’s sign with it’s parent, i.e. 14. Since 12 is right dominated, and 18, the unbalanced node is left dominated, we’ll have to make the node at 12’s place left dominated as well, so the desired rotation requires 12’s right child to be the pivot. We apply rotation, so now 12 is the left child of 14, which is the left child of 18, as follows —

I hope it’s clear what to do next as this is similar to what we saw in Fig. 2, so in that tree, we applied a left rotation, but here, since the orientation is the other way, we apply a right rotation, and as such, we balanced our tree —

Now that we have all of that out of the way, we can finally talk how this design of AVL-trees gives it such an efficient runtime. Let’s look at the tree in Fig. 1 again.

The height of this tree is 6, the number of nodes in the tree, so searching for 31 requires traversing through the whole tree until it reaches 31. While balancing the trees, we deal with the height of the subtrees, possibly changing that of the whole tree itself. As height depicts the worst-case, adjusting it also has an affect on the runtime itself.

The above tree, when adjusted, achieves a height of 3, as you can see in Fig. 4, so now as node traversal for 31 is halved, the runtime reduces by a lot as well. But what relationship does the runtime have with the height? Or in other words, how does the number of nodes affect the height of the tree?

Let’s look at the maximum number of nodes for each level can take —

And using this relationship, we are able to derive —

Therefore, h is O(log n), with log base 2 because it’s a binary tree.

We started off this section with searching a value, but I promised the same runtime for all three functions. For deletion, it again requires searching for the value, which we’ve proved takes O(log n) time, and then if the updated node is out of balance, rotations take place, possibly requiring a traversal along the height to check balance factors which should also take O(log n) at max, and as for insertion, inserting the node is constant, followed by possible rotations taking O(log n) time at the worse-case again. Thereby, proving the beauty that is an AVL-tree.

Related posts:

Some thoughts on all of the movies I watched this month. Just so there’s no confusion: 🔁 means I’ve previously seen the movie, and my rating scale is a little harsher than most people’s (if you’re…

The first time I saw a picture of her, my first impression was not that she was black, but her funny facial expressions (and Mr. Obama’s). I have never discriminated against any race, and never will…

Xanthan gum is the secret ingredient in this soup; 1/4 teaspoon added into the cream and broth makes the soup so thick and delicious, and you would never know it is not authentic “chowda.” This is…