sponding operation from the binary search tree after removing the targeted entrysubtrees may have to be rebalanced for examplesuppose we want to remove key from the avl tree in figure (aafter removing the leaf nodethe subtree rooted at node is out of balanceas shown in figure (ba left rotation has to be performed pivoting on node to correct the imbalanceas shown in figure ( > < ( ( (cfigure deletion that causes the avl tree to become unbalanced(athe node is located(bthe balance factors change showing an out-of-balance treeand (cthe tree after left rotation as with an insertionthe only subtrees that can become unbalanced are those along the path from the root to the original node containing the target rememberif the key being removed is in an interior nodeits successor is located and copied to the node and the successor' original node is removed in the insertion operationat most one subtree can become unbalanced after the appropriate rotation is performed on the subtreethe balance factors of the node' ancestors do not change thusit restores the height-balance property both locally at the subtree and globally for the entire tree this is not the case with deletion when subtree is rebalanced due to deletionit can cause the ancestors of the subtree to then become unbalanced this effect can ripple up all the way to the root node soall of the nodes along the path have to be evaluated and rebalanced if necessary implementation partial implementation of the map adt using balanced binary search tree is provided in listing the implementation of the non-helper methods is very similar to that of the binary search tree version since the traversal and search operations of the avl tree are identical to those of the binary search treethe valueof(method can use the bstsearch(helper method and the iter method can create an instance of the bstmapiterator of coursewe assume the implementation of these components are included within the avlmap class the