balanced binary search trees fig avl tree case step rotate toward againthe tree is still binary search tree and the height of the subtree in the position of the original pivot node is not changed by the double rotation figure illustrates this situation the pivot in this case is the root of the tree the node containing is the bad child the bad grandchild is the node containing (fig the imbalance in the tree is to the right of the pivot yet the is being inserted to the left of the bad child the first step is rotation to the right at the bad child this brings the upsomewhat helping to balance the right side of the tree the second stepdepicted in fig rotates to the left at the pivot bringing the whole tree into balance again the trickiest part of this algorithm is updating the balances correctly firstthe pivotbad childand bad grandchild contain the balances that may change if there is no bad grandchild then the pivot' and bad child' balances will be zero if there is bad grandchildas is the case herethen there is little more work to determining the balances of the pivot and the bad child when the bad grandchild existsits balance is after the double rotation the balances of the bad child and pivot depend on the direction of the rotation and the value of the new item and the bad grandchild' item this can be analyzed on case by case basis to determine the balances of both the pivot and bad grandchild in these cases in the next section we examine how the balances are calculated fig avl tree case step rotate away this copy belongs to 'acha