listing inserting an entry into an avl tree class avlmap recursive method to handle the insertion into an avl tree the function returns tuple containing reference to the root of the subtree and boolean to indicate if the subtree grew taller def _avlinsertselfsubtreekeynewitem )see if we have found the insertion point if subtree is none subtree _avltreenodekeynewitem taller true is the key already in the treeelif key =subtree data return (subtreefalsesee if we need to navigate to the left elif key subtree data (subtreetaller_avlinsertsubtree leftkeynewitem if the subtree grew tallersee if it needs rebalancing if taller if subtree bfactor =left_high subtree right _avlleftbalancesubtree taller false elif subtree bfactor =equal_high subtree bfactor left_high taller true else right_high subtree bfactor equal_high taller false otherwisenavigate to the right else key subtree data (nodetaller_avlinsertsubtree rightkeynewitem if the subtree grew tallersee if it needs rebalancing if taller if subtree bfactor =left_high subtree bfactor equal_high taller false elif subtree bfactor =equal_high subtree bfactor right_high taller true else right_high subtree right _avlrightbalancesubtree taller false return the results return (subtreetalleris out of balance and needs to be rebalanced regardless if the subtree is out of balancethe balance factor of the current subtree' root node has to be modified as discussed in the previous section if subtree did not grow tallernothing needs to be done