COP 3503H – Computer Science I – CLASS NOTES - DAY #26 SupplementMore on Tree RotationsCOP 3503H – Computer Science I – CLASS NOTES - DAY #26 SupplementMore on Tree RotationsSingle RotationsRecall that the insertion of a new node into an AVL tree could occur in one of fourdifferent ways (two of which are symmetric to each other):1. The new node is in the left subtree of the left child of a node.2. The new node is in the right subtree of the left child of a node.3. The new node is in the left subtree of the right child of a node.4. The new node is in the right subtree of the right child of a node.Cases 1 and 4 are symmetric as are cases 2 and 3.Whenever an insertion of case 1 or 4 occurs, the resulting tree will be unbalanced and asingle rotation can be used to rebalance the tree. Consider the following case 1situation (insertion in left subtree of a left child): -1 0 0initial AVL treeDay 26 Supplement- 1PSACBPSACBPSCBA-2 -1 0tree immediately after insertion into subtree AThe new node has been inserted into the left subtree (A) of node S which is the leftchild of node P. The tree is now unbalanced and is temporarily not an AVL tree. Torestore the balance in the tree and return it to the status of an AVL tree, a single rotationof S about P is needed as shown below: 00Rebalanced tree is now an AVL treeDay 26 Supplement- 2SPAB CExample – Case 1 Insertioninitial AVL tree initial balance factorsAVL tree after insertion of 20 balance factors after insertionPerform right rotation of 30 about 40 (40 is the unbalanced node).The steps in the right rotation are:Day 26 Supplement- 34030 503525-10 000204030 5035250-2-1 00-1204030 503525 503025 4035201. Interchange nodes 30 and 40.2. Interchange causes node 40 to move to right subtree of 30.3. Former right subtree of 30 becomes left subtree of 40.4. Left subtree of 30 is unchanged.5. Right subtree of 40 is unchanged.You should verify that the resulting tree is AVL balanced.Now consider a case 4 situation (insertion in right subtree of a right child):+1 0initial AVL tree +2 +1tree immediately after insertion into subtree BDay 26 Supplement- 4PSCBAPSCBAThe new node has been inserted into the right subtree (B) of node S which is the rightchild of node P. The tree is now unbalanced and is temporarily not an AVL tree. Torestore the balance in the tree and return it to the status of an AVL tree, a single rotationof S about P is needed as shown below: 0 0final AVL treeExample – Case 4 Insertioninitial AVL tree initial balance factorsDay 26 Supplement- 5SPBAC40503045 55+1000 06540503045 550+2+100 +1AVL tree after insertion of 65 balance factors after insertionPerform left rotation of 50 about 40 (40 is the unbalanced node).The steps in the left rotation are:1. Interchange nodes 40 and 50.2. Interchange causes node 40 to move to left subtree of 30.3. Former left subtree of 50 becomes the right subtree of 40.4. Left subtree of 40 is unchanged.5. Right subtree of 50 is unchanged.Notice the symmetry of the two final AVL trees after the insertions and subsequentrebalancing.Day 26 Supplement- 665040503045 55 3050554045 650case 1 final AVL tree case 4 final AVL treeDouble RotationsCases 2 and 3 when inserting into an AVL tree require a double rotation to rebalancethe tree. Case 2 occurs when the new node is in the left subtree of the right child of anode. Case 3 occurs when the new node is in the right subtree of the right child of anode. As before, cases 2 and 3 are symmetric. Consider the following case 2 situation (insertion in left subtree of a right child): 0 +1 0initial AVL tree -2Day 26 Supplement- 7SPBACCBAPSGPSDACBGPSDACB+2 -1tree immediately after insertion into subtree BThe new node has been inserted into subtree B which is left subtree of node S which isa right child of P. The tree is now unbalanced and is temporarily not an AVL tree. Torestore the balance in the tree and return it to the status of an AVL tree, a doublerotation of S about P followed by S about G is needed as shown below. While thedouble rotation may seem confusing it is in reality two single rotations as shownbelow: (1) rotate G’s grandchild about G’s child [rotate S about P] initial unbalanced treeDay 26 Supplement- 8GPSDACBGSPDACBrotation of S about P (first rotation – tree still unbalanced)rotation of S about G (second rotation – tree becomes balanced)Day 26 Supplement- 9SPDA CBGSP GDA CBfinal AVL tree (balanced)Example – Case 2 Insertion (double left/right rotation)initial AVL tree initial balance factorsAVL tree after insertion of 32 balance factors after insertionPerform double rotation: 1st do 35 about 30 followed by 35 about 40.Day 26 Supplement- 1040503025 35-1000 040503025 3532-20+10 -1040503025 3532405035303225tree after insertion tree after first rotation of 35 about 30balance factors after first rotation rotate 35 about 40tree after second rotation of 35 about 40 final balance factorsThe steps in the double rotation are:1. Interchange parent and grandparent of new node (nodes 35 and 30).2. Interchange previous parent and great-grandparent (noded 35 and 40).Example – Case 3 Insertion (double right/left rotation)Day 26 Supplement- 11step 1step 23540302532 500+1000 0-20-20004050353032254030 506545+10 000initial AVL tree initial balance factorsAVL tree after insertion of 48 balance factors after insertionPerform double rotation: 1st do 45 about 50 followed by 45 about 40.Day 26 Supplement- 12step 14030 50654548+20 -10+104030 506545484030 455048 65tree after insertion tree after first rotation of 45 about 50balance factors after first rotation rotate 45 about 40tree after second rotation of 45 about 40 final balance factorsThe steps in the double rotation are:1. Interchange parent and grandparent of new node (nodes 35 and 30).2. Interchange previous parent and great-grandparent (noded 35 and 40).Day 26 Supplement- 13step 24540 506548300-1 0000+20 +200 04030 455048 65Day 26 Supplement-