Cases of Rotation of AVL Tree

 

The single rotation does not seem to restore the balance. We will re-visit the tree and rotations to identify the problem area. We will call the node that is to be rotated as a (node requires to be re-balanced). Since any node has at the most two children, and a height imbalance requires that a’s two sub-trees differ by two (or –2), the violation will occur in four cases:

1. An insertion into left subtree of the left child of a.

2. An insertion into right subtree of the left child of a.

3. An insertion into left subtree of the right child of a.

4. An insertion into right subtree of the right child of a.

The insertion occurs on the outside (i.e., left-left or right-right) in cases 1 and 4. Single rotation can fix the balance in cases 1 and 4.

Insertion occurs on the inside in cases 2 and 3 which a single rotation cannot fix.

Let’s see the figure below:

We have shown, single right notation to fix case 1. Two nodes k2 and k1 are shown in the figure, here k2 is the root node (and also the a node, k1 is its left child and Z shown in the triangle is its right child. The nodes X and Y are the left and right subtrees of the node k1. A new node is also shown below to the triangle of the node X, the exact position (whether this node will be right or left child of the node X) is not mentioned here. As the new node is inserted as a child of X that is why it is called an outside insertion, the insertion is called inside if the new node is inserted as a child of the node Y. This insertion falls in case 1 mentioned above, so by our definition above, single rotation should fix the balance. The k2 node has been rotated single time towards right to become the right child of k1 and Y has become the left child of k2. If we traverse the tree in inorder fashion, we will see that the output is same:

X k1 Y k2 Z

Consider the the figure below:

In this figure (Fig 21.14), the new node has been inserted as a child node of Z, that is why it is shown in bigger size covering the next level. Now this is an example of case 4 because the new node is inserted below the right subtree of the right child of the root node (a). One rotation towards should make it balanced within limits of AVL tree. The figure on the right is after rotation the node k1 one time towards left. This time node Y has become the right child node of the node k1.

In our function of insertion in our code, we will do insertion, will compute the balance factors for nodes and make rotations.

Now, we will see the cases 2 and 3, these are not resolved by a single rotation.

We see here that the new node is inserted below the node Y. This is an inside insertion. The balance factor for the node k2 became 2. We make single rotation by making right rotation on the node k2 as shown in the figure on the right. We compute the balance factor for k1, which is –2. So the tree is still not within the limits of AVL tree. Primarily the reason for this failure is the node Y subtree, which is unchanged even after making one rotation. It changes its parent node but its subtree remains intact. We will cover the double rotation in the next lecture.

It is very important that you study the examples given in your text book and try to practice the concepts rigorously.

Now the question arises whether the single rotation help us in balancing the tree or not. If the new node is inserted in the left subtree of the a’s left child or in the right subtree of a’s right child, the balance will be restored through single rotation. However, if the new node goes inside the tree, the single rotation is not going to be successful in balancing the tree.

We face four scenarios in this case. We said that in the case-1 and case-4, single rotation is successful while in the case-2 and case-3 single rotation does not work. Let’s see the tree in the diagram given below.

In the above tree, we have a node as k2, which has a left child as k1. Whereas X and Y are its left and right children. The node k2 has a right child Z. Here the newly inserted node works as the left or right child of node Y. Due to this insertion, one level is increased in the tree. We have applied single rotation on the link of k1 and k2. The right side tree in the figure is the post-rotation tree. The node k1 is now at the top while k2 comes down and node Y changes its position. Now if you see the levels of the node, these are seen same. Have a look on the level of the a node i.e. k1 which reflects that the difference between the left and right side levels is still 2. So the single rotation does not work here.

Let’s see how we can fix that problem. A fresh look on the following diagram will help us understand the problem.

Here k2 is the root node while k1 and Z are the right and left children respectively. The new node is inserted under Y so we have shown Y in a big triangle. The new node is inserted in the right subtree of k1, increasing its level by 1. Y is not empty as the new node was inserted in it. If Y is empty, the new node will be inserted under k1. It means that Y has a shape of a tree having a root and possibly left and right subtrees. Now view the entire tree with four subtrees connected with 3 nodes. See the diagram below.

We have expanded the Y and shown the root of Y as K2, B and C are its left and right subtrees. We have also changed the notations of other nodes. Here, we have A, B, C and D as subtrees and k1, k2 and k3 as the nodes. Let’s see where the new node is inserted in this expanded tree and how can we restore its balance. Either tree B or C is two levels deeper than D. But we are not sure which one is deeper. The value of new node will be compared with the data in k2 that will decide that this new node should be inserted in the right subtree or left subtree of the k2. If the value in the new node is greater than k2, it will be inserted in the right subtree i.e. C. If the value in the new node is smaller than k2, it will be inserted in the left subtree i.e. B. See the diagram given below:

We have seen the both possible locations of the new node in the above diagram. Let’s see the difference of levels of the right and left subtrees of the k3. The difference of B or C from D is 2. Therefore the expansion of either of B or C, due to the insertion of the new node, will lead to a difference of 2. Therefore, it does not matter whether the new node is inserted in B or C. In both of the cases, the difference becomes 2. Then we try to balance the tree with the help of single rotation. Here the single rotation does not work and the tree remains unbalanced. To re-balance it, k3 cannot be left as the root. Now the question arises if k3 cannot become root, then which node will become root? In the single rotation, k1 and k3 were involved. So either k3 or k1 will come down. We have two options i.e. left rotation or right rotation. If we turn k1 into a root, the tree will be still unbalanced. The only alternative is to place k2 as the new root. So we have to make k2 as root to balance the tree. How can we do that?

If we make k2 the root, it forces k1 to be k2‘s left child and k3 to be its right child. When we carry out these changes, the condition is followed by the inorder traversal. Let’s see the above tree in the diagram. In that diagram, the k3 is the root and k1 is its left child while k2 is the right child of k1. Here, we have A, B, C and D as subtrees. You should know the inorder traversal of this tree. It will be A, k1, B, k2, C, k3 and D where A, B, C and D means the complete inorder traversal of these subtrees. You should memorize this tree traversal.

Now we have to take k2 as the root of this tree and rearrange the subtrees A, B, C and D. k1 will be the left child of k2 while k3 is going to be its right child. Finally if we traverse this new tree, it will be the same as seen above. If it is not same, it will mean that there is something wrong in the rotation. We have to find some other solution. Now let’s see how we can rotate our tree so that we get the desired results.

Left-right double rotation to fix case 2

We have to perform a double rotation to achieve our desired results. Let’s see the diagram below:

On the left side, we have the same tree with k3 as its root. We have also shown the new nodes as new and new’ i.e. the new node will be attached to B or C. At first, we will carry out the left rotation between k1 and k2. During the process of left rotation, the root k1 comes down and k2 goes up. Afterwards, k1 will become the left child of k2 and the left subtree of k2 i.e. B, will become the right subtree of k1. This is the single rotation. You can see the new rotated tree in the above figure. It also shows that the B has become the right child of the k1. Moreover, the new node is seen with the B. Now perform the inorder traversal of this new rotated tree. It is A, k1, B, k2, C, k3 and D. It is same as witnessed in case of the inorder traversal of original tree. With this single rotation, the k2 has gone one step up while k1 has come down. Now k2 has become the left child of k3. We are trying to make the k2 the root of this tree. Now what rotation should we perform to achieve this?

Now we will perform right rotation to make the k2 the root of the tree. As a result, k1 and k2 have become its left and right children respectively. The new node can be inserted with B or C. The new tree is shown in the figure below:

Now let’s see the levels of new and new’. Of these, one is the new node. Here you can see that the levels of new, new’ i.e. A and D are the same. The new tree is now a balanced one. Let’s check the inorder traversal of this tree. It should be the same as that of the original tree. The inorder traversal of new tree is A, k1, B, k2, C, k3 and D, which is same as that of the original tree.

This is known as double rotation. In double rotation, we perform two single rotations. As a result, the balance is restored and the AVL condition is again fulfilled. Now we will see in which order, the double rotation is performed? We performed a left rotation between k1 and k2 link, followed by a right rotation.

Right-left double rotation to fix case 3

In case, the node is inserted in left subtree of the right child, we encounter the same situation as discussed above. But here, we will perform right rotation at first before going for a left rotation. Let’s discuss this symmetric case and see how we can apply double rotation here. First we perform the right rotation.

Here k1 is the root of the tree while k3 is the right child of the k1. k2 is the inner child. It is the Y tree expanded again here and the new node will be inserted in the k2’s right subtree C or left subtree B. As we have to transform the k2 into the root of the tree, so the right rotation between the link k2 and k3 will be carried out. As a result of this rotation, k2 will come up and k3 will go down. The subtree B has gone up with the k2 while subtree C is now attached with the k3. To make the k2 root of the tree, we will perform the left rotation between then k1 and k2. Let’s see this rotation in the figure below:

In the above figure at the right side, we have the final shape of the tree. You can see that k2 has become the root of the tree. k1 and k3 are its left and right children respectively. While performing the inorder traversal, you will see that we have preserved our inorder traversal.

We have started this activity while building an example tree. We inserted numbers in it. When the balance factor becomes more than one, rotation is performed. During this process, we came at a point when single rotation failed to balance the tree. Now there is need to perform double rotation to balance the tree that is actually two single rotations. Do not take double rotation as some complex function, it is simply two single rotations in a special order. This order depends on the final position of the new node. Either the new node is inserted at the right subtree of the left child of a node or at the left subtree of the right child of a node. In first case, we have to perform left-right rotation while in the second case, the right-left rotation will be carried out.

Let’s go back to our example and try to complete it. So far, we have 1, 2, 3, 4, 5, 6, 7 and 16 in the tree and inserted 15 which becomes the left child of the node 16. See the figure below:

Here we have shown X, Y and Z in case of the double rotation. We have shown Y expanded and 15 is inside it. Here we will perform the double rotation, beginning with the right rotation first.

We have identified the k1, k2 and k3 nodes. This is the case where we have to perform right-left double rotation. Here we want to promote k2 upwards. For this purpose, the right rotation on the link of k2 and k3 i.e. 15 and 16 will be carried out.

The node 15 now comes up while node 16 has gone down. We have to promote k2 to the top and k3 and k1 will become its right and left children respectively. Now we will perform left rotation on the link of k1 and k2 i.e. 7 and 15. With this left rotation, 15 goes up and 7 and 16 become its left and right children respectively.

Here we have to check two things. At first, the tree is balanced or not i.e. the AVL condition is fulfilled or not. Secondly we will confirm that the inorder traversal is preserved or not. The inorder traversal should be the same as that of the inorder traversal of original tree. Let’s check these two conditions. The depth of the left subtree of node 4 is 2 while the depth of the right subtree of node 4 is three. Therefore, the difference of the levels at node 4 is one. So the AVL condition is fulfilled at node 4. At node 6, we have one level on it left side while at the right side of node 6, there are two levels. As the difference of levels is one, therefore node 6 is also balanced according to the AVL condition. Similarly other nodes are also fulfilling the AVL condition. If you see the figure above, it is clear that the tree is balanced.

We are doing all this to avoid the link list structure. Whenever we perform rotation on the tree, it becomes clear from the figure that it is balanced. If the tree is balanced, in case of searching, we will not have to go very deep in the tree. After going through the mathematical analysis, you will see that in the worst case scenario, the height of the tree is 1.44 log₂ n. This means that the searching in AVL is logarithmic. Therefore if there are ten million nodes in an AVL tree, its levels will be roughly as log₂(10 million) which is very few. So the traversal in an AVL tree is very simple.

Let’s insert some more nodes in our example tree. We will perform single and double rotations, needed to make the tree balanced. The next number to be inserted is 14. The position of node 14, according to the inorder traversal, is the right child of 7. Let’s see this in the diagram as:

The new node 14 is inserted as the right child of 7 that is the inner subtree of 15. Here we have to perform double rotation again. We have identified the k1, k2 and k3. k2 has to become the root of this subtree. The nodes k1 and k3 will come down with their subtrees while k2 is going to become the root of this subtree. After the right rotation the tree will be as:

With the right rotation, k2 has come one step up while k3 has been turned into the right child of k2 but k1 is still up. Now we will perform a left rotation on the link of k1 and k2 to make the k2 root of this subtree. Now think that after this rotation and rearrangement of node what will be the shape of the tree.

After the double rotation, the final shape of the tree will be as:

k2 has become the root of the subtree. k1 has attained the role of the left child of k2 and k3 has become the right child of the k2. The other nodes 5, 14 and 16 have been rearranged according to the inorder traversal. The node 7 has come up where as node 6 and 15 have become its left and right child. Now just by viewing the above figure, it is clear that the tree is balanced according to the AVL condition. Also if we find out its inorder traversal, it should be the same as the inorder traversal of original tree. The inorder traversal of the above tree is 1, 2, 3, 4, 5, 6, 7, 14, 15, and 16. This is in sorted order so with the rotations the inorder traversal is preserved.

Let’s insert some more numbers in our tree. The next number to be inserted is 13.

We have to perform single rotation here and rearrange the tree. It will look like as:

The node 7 has become the root of the tree. The nodes 4, 2, 1, 3, 6, 5 have gone to its left side while the nodes 15, 14, 13, 16 are on its right side. Now try to memorize the tree which we build with these sorted numbers. If you remember that it looks like a link list. The root of that tree was 1. After that we have its right child as 2, the right child of 2 as 3, then its right child 4 and so on up to 16. The shape of that tree looks exactly like a linked list. Compare that with this tree. This tree is a balanced one. Now if we have to traverse this tree for search purposes, we have to go at the most three levels.

Now you must be clear why we need to balance the trees especially if we have to use the balanced search trees. While dealing with this AVL condition, it does not matter whether the data, provided to a programmer is sorted or unsorted. The data may be sorted in ascending order or descending order. It may contain alphabets or names in any order. We will keep our tree balanced during the insertion and tree will be balanced at each point. Our tree will not be balanced in the end, it will be balanced with each insertion. It will not be completely balanced. At the maximum, if we pick any node, the difference in the levels of its right subtree and left subtree will not be more than 1.

Now if we have 9 or 10 nodes in the tree and take log of this, it will be near 3. Therefore our tree has three levels after that there are its leaf nodes. Please keep this in mind that originally we have thought BST as an abstract data type. We have defined operations on it like insert, remove and the major method was find. The find method takes a data item and searches the tree. It will also show that this data item exists or not in the tree. We also right findMin and findMax methods. In case of a BST, we can find the minimum and maximum value in it. The minimum will be the left most node of the tree while the right most node of BST will give the maximum value. You can confirm it by applying this on the above tree.

Technorati Tags: ds tutorial,data structure tutorial,tree data structure,trees in data structure,tree ds,tree traversal data structure,tree types,types of trees,binary trees,binary search trees,bst,bst data structure,bst ds,complete binary search tree,non tree structure,linear tree,avl tree,avl tree traversal,avl data structure,avl ds,avl tree rotation,rotation of avl tree,avl tree tutorial