as was the case for the insert dictionary operationwe begin the implementation of the remove dictionary operation on an avl tree by using the algorithm for performing this operation on regular binary search tree the added difficulty in using this approach with an avl tree is that it may violate the height-balance property in particularafter removing an internal node with operation remove external and elevating one of its children into its placethere may be an unbalanced node in on the path from the parent of the previously removed node to the root of (see figure in factthere can be one such unbalanced node at most (the justification of this fact is left as exercise - figure removal of the entry with key from the avl tree of figure (aafter removing the node storing key the root becomes unbalanced(ba (singlerotation restores the heightbalance property as with insertionwe use trinode restructuring to restore balance in the tree in particularlet be the first unbalanced node encountered going up from toward the root of alsolet be the child of with larger height (note that node is the child of that is not an ancestor of )and let be the child of defined as followsif one of the children of is taller than the otherlet be the taller child of yelse (both children of have the same height)let be the child of on the same side as (that isif is left childlet be the left child of yelse let be the right child of yin any casewe then perform restructure(xoperationwhich restores the height-balance property locallyat the subtree that was formerly rooted at and is now rooted at the node we temporarily called (see figure unfortunatelythis trinode restructuring may reduce the height of the subtree rooted at by which may cause an ancestor of to become unbalanced soafter rebalancing zwe continue walking up looking for unbalanced nodes if we