Insertions in AVL Tree

Today we shall explore AVL trees which is a special kind of binary search trees. Binary Search Trees or BSTs have the property that each node would have a maximum of two nodes and the child node on the right would be greater than the parent node and the child node on the left would be lesser. This should ideally provide us with O(log n) search time but under certain special conditions the performance could degrade to O(n) which is nothing better than a linked list. This could happen if the input data is in a sorted order or mostly sorted order. For eg. Consider the input data is A, B, C, D, E. In a normal binary search tree this would lead to A being inserted as the root and then B to the right of B, and C to the right of B and so on leading to a linked list. Hence to find the nth element we will have to make n traversals leading to O(n) worst case performance.

To solve this problem there are a variety of self balancing trees like AVL, red-black, splay trees,2-3 trees, AA trees etc. AVL is probably the most simplest of them and in this case lets look at insertions in an AVL tree which is much simpler than deletion. AVL maintains it’s height by rebalancing or rotating around unbalanced nodes.

When is a node said to be unbalanced? A node is unbalanced when the Absolute(height of the left sub-tree – height of right sub-tree) is greater than 1. The height of a tree is the length of the longest path from the root to any of the nodes of the trees. For eg. In the tree below the heigh of left tree of B is 2 whereas right tree is 0 and hence it has a balance factor of -2, C is unbalanced too but E is balanced because height of B is 3 and so is of J.

An unbalance can happen in only 4 ways divided into these two patterns appropriately named zigzig(outside) and zigzag(inside). Consider N is the node that became unbalanced and let the left child node of N be M and right child be O (i.e M <- N -> 0), then this unbalance can be categorized into a :

1. ZigZig pattern or Outside Cases that require single rotation :
   1. Unbalance has occurred because of a node insertion into left sub-tree of left child of N (i.e. M). In this case we move M up and node N down as the right child of M. Since N is greater than M the BST property is maintained since N is to the right of M. Any right sub-tree of M becomes the left sub-tree of N since M was smaller than M and any subtree of M will be smaller than N and hence should fit as the left child node of N.
   2. Unbalance has occurred because of a node insertion into right sub-tree of right child of N(i.e. O). In this case we O up and node N down as the left child of O. Since O was always greater than N, N being on the left child node of O satisfies the BST property. Any left sub-tree of O becomes the right sub-tree of N.
2. ZigZag patterns or Inside Cases that require double rotation :
   1. Unbalance has occurred because of a node insertion into right sub-tree of left child of N (i.e M). Let L be the root of right sub-tree of M. We first move L up and M down as the left child node of L. This now becomes a zigzag pattern and we now resolve it by moving L up to N and rotating N down as the right child of L.
   2. Unbalance has occurred because of a node insertion into left sub-tree of right child of N(i.e O). Let P be the root of the left sub-tree of O. First move P up and O down as the right child node of P. This now becomes a zigzig pattern. Now pull P up N down as the left child node of P.

I understand it is difficult to comprehend the above 4 cases and I won’t describe each one of these specific examples right now but down below where we see AVL insertion in action there are plenty of places where the above cases are described.

Right now in the picture above the insertion of O has caused C to be unbalanced. O was inserted into the left sub-tree of a right child of C(case d) and this can be solved by a zigzag rotation. If O was inserted to the right of D then it would be a zigzag pattern i.e an insertion into the left sub-tree of the left child caused the unbalance(case a).

Having said this lets jump into seeing how insertions work in an AVL tree.

Consider a queue like this:

We insert K first as the root. A is inserted after K. Since A is lesser than K and an AVL tree after all is a binary search tree and hence has to follow all the rules of BSTs A is inserted to the left of K. Next H is inserted to the right of A since it is greater than A. Immediately K is unbalanced by a factor of 2 and we need to rebalance it.

The unbalance has happened because H was inserted into the right sub-tree of the left child (case c). We apply the zigzag rule. We resolve this unbalance using a double rotation. The first rotation simplifies the problem to a zigzig problem and maintains the rules of BST. We rotate A and H. So H becomes the parent of A but A is smaller than H so A goes to the left side of H thereby maintaining a BST.

First rotation:

But K is still unbalanced so we do a second rotation sending K down as the right child of H. Now H becomes root.

Second Rotation:

Now we have a balanced AVL tree. You might say this is a simple case and what would happen if say H had a left sub-tree? When A is placed as the left child of H where would the previous left child tree of H go? The answer is that it will be handed down to the right child node of A since that was previously occupied by H. In a BST every node that goes down the right child node of a node has to be greater than the node itself. So every node in the left sub-tree of H has to be greater than A and hence making it the new right child node of A should not break any rules of BST.

Add I:

Add J and tree is unbalanced:

Apply zig zag rule again. Push J up and I down as the left child node.

First rotation:

For the second rotation push J up again and K down as the child node.

Second rotation:

Add B:

Add F and tree is unbalanced:

A is now unbalanced. Here we come to our first example of a zigzig pattern. A zigzig pattern is simpler than a zigzag pattern to resolve and we can do so with a single rotation. Push B up and A down as the left child of B. The tree is now balanced.

Add E:

Add G:

Add C and B is now unbalanced:

We will apply the zigzag rule since B->F->E forms a zigzag pattern. The addition is to the left sub-tree of the right node of the unbalanced node.

For the first rotation we will move E up and F as the right child node but this still leaves B unbalanced by -2. We have to do the second rotation of the zigzag pattern by moving E up and B as the left child node. But where will the current left child of E go? C will now become the right child node of B. Any node that is placed to the right side of B previously is always greater than B and hence any sub-tree starting from than node can placed as the right child node of B as explained previously.

Second rotation balances the tree:

Adding D unbalances the tree again this time at ‘H’:

You many look at the diagram and say that the zigzag rule should be applied here. But look carefully at the definition of the rules. The insertion is to the left sub-tree starting from B of the left child node E of the unbalanced(affected) node in this case H. So the zigzig rule should be applied here since the change is made to the left sub-tree of the left node of ‘H’. H is rotated down and E becomes the new root.

Add M and the tree is still balanced:

Add N:

Add N and J is now unbalanced by -2. We will resolve this by using the zigzig pattern. Since J is the affected node we will pull K up and send J down restoring the balance.

Last we will add L.

After this all elements are added and we have a balanced AVL tree with no nodes having a balance factor greater than 1.