deletion recall that deletion from regular binary search tree results in the structural removal of node having either zero or one children such change may violate the height-balance property in an avl tree in particularif position represents the parent of the removed node in tree there may be an unbalanced node on the path from to the root of (see figure in factthere can be at most one such unbalanced node (the justification of this fact is left as exercise - ( (bfigure deletion of the item with key from the avl tree of figure (aafter removing the node storing key the root becomes unbalanced(ba (singlerotation restores the height-balance property as with insertionwe use trinode restructuring to restore balance in the tree in particularlet be the first unbalanced position encountered going up from toward the root of alsolet be the child of with larger height (note that position 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 the left child of zlet be the left child of yelse let be the right child of yin any casewe then perform restructure(xoperation (see figure the restructured subtree is rooted at the middle position denoted as in the description of the trinode restructuring operation the height-balance property is guaranteed to be locally restored within the subtree of (see exercises - and - 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 positions if we find anotherwe perform restructure operation to restore its balanceand continue marching up looking for moreall the way to the root stillsince the height of is (log )where is the number of entriesby proposition (log ntrinode restructurings are sufficient to restore the height-balance property