the nodes in an avl tree must store their balance factor in addition to the keydataand two child links the avltreenode is provided in lines - of listing we also create and initialize three named constants to represent the three balance factor values by using named constantswe avoid possible confusion in having to remember what value represents which of the possible balance factors the implementation of the insertion operation is divided into several helper methods for better modular solution firstwe provide helper methods for performing the left and right rotationsas shown in listing right rotation on given pivot node is performed using avlrotateright(the operation is illustrated in figure the avlrotateleft(function handles left rotationas illustrated in the top of figure both methods return reference to the new root node of the subtree after the rotation listing helper functions for performing the avl tree rotations class avlmap rotates the pivot to the right around its left child def _avlrotaterightselfpivot ) pivot left pivot left right right pivot return rotates the pivot to the left around its right child def _avlrotateleftselfpivot ) pivot right pivot right left left pivot return when subtree becomes unbalancedwe have to determine which of the four possible cases caused the event cases and occur when the left subtree of the pivot node is two levels higher than the right subtreewhereas cases and occur when the right subtree becomes two levels higher than the left we divide the cases into two groups based on which subtree of the pivot node is higher the avlleftbalance(methodprovided in listing handles the rotations when the left subtree is higher to distinguish between the two caseswe have to examine the balance factor of the pivot node' left child case one occurs when the left child has factor of left high (its left child is higherfor this casethe balance factors are adjusted appropriately and right rotation is performed using the avlrightrotate(methodas shown in lines - case occurs when the balance factor of the left child of the pivot node is right high note that the case of the pivot' left child having equal balance can never occurso we do not have to check for this condition after setting the balance factorscase requires double rotationas shown in lines - we first perform left rotation on the right child (cof the pivot node the root node of the subtree resulting from this rotation becomes the new left child of the pivot node right rotation is then performed on