{"id":340,"date":"2018-07-19T06:16:52","date_gmt":"2018-07-19T06:16:52","guid":{"rendered":"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=340"},"modified":"2018-12-12T10:36:18","modified_gmt":"2018-12-12T10:36:18","slug":"insertion-and-deletion-avl-trees","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/chapter\/insertion-and-deletion-avl-trees\/","title":{"rendered":"Insertion and Deletion – AVL Trees"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\n \r\n\r\n \r\n

Welcome to the e-PG Pathshala Lecture Series on Data Structures. We have understood the basic concept AVL, a balanced binary search tree. In this module we will discuss the insertion and deletion operations of AVL trees and the rebalancing carried out for re-establishing the balance while maintaining the binary search property.<\/p>\r\n \r\n\r\nLearning Objectives<\/strong>\r\n\r\n \r\n\r\nThe learning objectives of the module are as follows:\r\n\r\n \r\n\r\n\u2022 To understand the Insertion operations of AVL Trees\r\n\r\n\u2022 To discuss Deletion from AVL Trees\r\n\r\n\u2022 To Outline the Pros and Cons of AVL Trees\r\n\r\n \r\n\r\n24.1 Insertion into AVL Trees<\/strong>\r\n\r\n \r\n

The first step of insertionof a node into the AVL tree is a normal insertion using a BST insertion algorithm. However in addition we have to rebalance the tree if an imbalance occurs. As we have discussed in the last module, an imbalance occurs if a node's balance factor changes from -1 to -2 or from+1 to +2.Rebalancing is done at the deepest or lowest unbalanced ancestor of the inserted node.<\/p>\r\n \r\n\r\nThere are three cases that can happen during insertion:\r\n\r\n \r\n

1. Insertion that does not cause an imbalance.<\/p>\r\n

2.Same side (left-left or right-right) insertion that causes an imbalance. This type of insertion requires a single rotation to rebalance.<\/p>\r\n

3.Opposite side (left-right or right-left) insertion that causes an imbalance. This type of insertion requires a double rotation to rebalance.<\/p>\r\n \r\n\r\n24.2 Insertion Algorithm<\/strong>\r\n\r\n \r\n

The first step of the insertion algorithm for AVL trees is the same as insertion into a binary search tree. Here we first find a place for the value to be inserted, and then insert it. Now comes the next step of insertion into the AVL tree which is searching back from the inserted node looking for imbalance. If there is an imbalancewhen a new element is added as the outside grandchild (that is the left grandchild of a left\u00a0child (left-left) or the right grandchild of a right child (right-right))(Figure 24.1 (a)) we perform single rotation and exit. When a new item is added as an inside grandchild (Figure 24.1 (b)), the imbalance is fixed with a double right or left rotation. As already discussed in the previous module an inside grandchild is when we have left grandchild of a right child (left-right) or the right grandchild of a left child (right-left)).<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\n \r\n

As we have already discussed in the previous module the insert operation may cause balance factor to become +2 or \u20132 for some node. Now only nodes on the path from the insertion point to the root node have possibly changed in height. Therefore after insertion, we go back up to the root node by node, updating heights as we go. If a new balance factor (the difference hleft-hright) is +2 or \u20132, we need to adjust the balance of the tree by rotation<\/em> around the node. Now let us consider a validAVL sub-tree (Figure 24.2). Before the insertion into the subtree M the tree was a valid AVL tree, but after the insertion the AVL property is violated at node j where the balance factor has become +2.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n24.3 Rebalancing<\/strong>\r\n\r\n \r\n

Rebalancing is done at the deepest unbalanced ancestor of the inserted node. Now let the node that needs rebalancing be denoted as X. The rebalancing is performed through four separate types of rotations as given below:<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\u00a0 \u00a0 Outside Cases (require single rotation) :<\/strong>\r\n\r\n \r\n\r\n1.\u00a0 Insertion into left subtree of left child of X - (Single Right Rotation)<\/strong>\r\n\r\n2.\u00a0 Insertion into right subtree of right child of X \u2013 (Single Left Rotation)<\/strong>\r\n\r\n \r\n\r\nInside Cases (require double rotation) :<\/strong>\r\n\r\n \r\n\r\n3.\u00a0 Insertion into right subtree of left child of X \u2013 (Left-Right Rotation)<\/strong>\r\n\r\n4.\u00a0 Insertion into left subtree of right child of X \u2013 (Right-Left Rotation)<\/strong>\r\n\r\n \r\n\r\n24.3.1 Insertion into left sub-tree of left child of X<\/strong>\r\n\r\n \r\n

Let us consider the first case of insertion into left sub-tree of left child of X<\/strong> (Figure 24.3). Here we have inserted 7 as left sub-tree of left child (8) of X (9). It is at X that the balancing is violated with balance factor of X becoming +2. Now this node X is the pivot. This imbalance occurred when the new element (7) was added to the left sub-tree of the outside left grandchild that is we have the case of single right<\/strong> rotation.<\/strong><\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n

Now we carry out single right rotation of 8 about 9. In this case 8 becomes the right child of the parent (6) of 9 while 9 becomes the right child of 8. The BST property of the AVL tree is now maintained.<\/p>\r\n \r\n\r\n24.3.2 Insertion into right sub-tree of right child of X<\/strong>\r\n\r\n \r\n

Let us consider the second case of insertion into right sub-tree of right child of<\/strong> X <\/strong>(Figure 24.4). Here we have inserted 45 as right sub-tree of right child (40) of X\u00a0(35). It is at X that the balancing is violated with balance factor of X becoming -2. Now the node X is the pivot. This imbalance occurred when the new element (45) was added to the right sub-tree of the outside right grandchild that is we have the case of <\/span>single left rotation.<\/strong>Now we carry out single left rotation of 40 about 35. In this case 40 becomes the right child of the parent (30) of 35 while 35 becomes the left child of 40. The BST property of the AVL tree is now maintained.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n

Let us consider the third case of insertion into left sub-tree of right child of X<\/strong> (Figure 24.5). Here we have inserted 34 as left sub-tree of right child (40) of X (30). Balance is violated at X balance factor becoming -2. Now we carry out two<\/strong> rotations that is a right rotation followed by a left rotation<\/strong>:<\/p>\r\n\r\n