balanced binary search trees fig avl tree case left rotation new value under bad child in the opposite direction of the imbalance for instancethe subtree in fig is weighted to the left and the new node is inserted to the right of the bad child an analogous situation occurs when the subtree is weighted to the right and the new node is inserted into the left subtree of the bad child when either situation occurs double rotation is needed to bring it back into balance figure show that there are two possible subcases there are actually three possible subcases it is possible there is no bad grandchild in that casethe newly inserted node will end up in the location that would have been occupied by the bad grandchild otherwise the new node might be inserted to the left or right of the bad grandchildwhich is node in fig either waythe first step in fig is to rotate left at the bad childnode then right rotation at the pivotnode bcompletes the rebalancing of the tree againthe trickiest part of this implementation is the calculation of the balance of each node the bad grandchild and new pivot nodenode in fig always has balance of if there is no bad grandchildthen the new pivot node is the newly inserted value if there was bad grandchildand if the new item was less than the bad grandchild' itemthe balance of the bad child is and the balance of the old pivot is if the new item was inserted to the right of the bad grandchild then the balance of the bad child is - and the balance of the old pivot is all other balances remain the same including balances above the pivot because the overall height of the tree before inserting the new value and after inserting the new value has not changed againan analogous situation occurs in the mirror image of fig when new value is inserted into left subtree of bad child which is in the right subtree of the pivot and which is already weighted more heavily to the rightthen double rotation is also requiredrotating first right at the bad child and then left at the pivot this copy belongs to 'acha