search trees listing helper functions used to rebalance avl subtrees class avlmap rebalance node when its left subtree is higher def _avlleftbalanceselfpivot )set to point to the left child of the pivot pivot left see if the rebalancing is due to case if bfactor =left_high pivot bfactor equal_high bfactor equal_high pivot _avlrotaterightpivot return pivot otherwisea balance from the left is due to case else change the balance factors if bfactor =left_high pivot bfactor right_high bfactor equal_high elif bfactor =equal_high pivot bfactor equal_high bfactor equal_high else bfactor =right_high pivot bfactor equal_high bfactor left_high all three cases set ' balance factor to equal high bfactor equal_high perform the double rotation pivot left _avlrotateleftl pivot _avlrotaterightpivot return pivot the pivot noderesulting in the grandchild (gof the original pivot node becoming the new root node the avlrightbalance(method can be implemented in similar fashion the actual implementation is left as an exercise the insert operation for the binary search tree returned reference to the existing subtree or the new nodedepending on the current invocation of the recursive function when inserting into an avl treethe method must also return boolean flag indicating if the subtree grew taller in order to return both valuesthe avlinsert(functionshown in listing returns tuple with the first element containing the node reference and the second containing the boolean flag finding the location of the new key and linking its node into the tree uses the same navigation technique as in the binary search tree the real difference between the insertions into bst and an avl tree occurs during the unwinding of the recursion we have to check to see if the subtree we just visited has grown taller taller child subtree means we have to check to see if the current subtree