"search-and-repairstrategy in particularlet be the first node we encounter in going up from toward the root of such that is unbalanced (see figure alsolet denote the child of with higher height (and note that node must be an ancestor of wfinallylet be the child of with higher height (there cannot be tie and node must be an ancestor of walsonode is grandchild of and could be equal to since became unbalanced because of an insertion in the subtree rooted at its child ythe height of is greater than its sibling we now rebalance the subtree rooted at by calling the trinode restructuring methodrestructure( )given in code fragment and illustrated in figures and trinode restructuring temporarily renames the nodes xyand as aband cso that precedes and precedes in an inorder traversal of there are four possible ways of mapping xyand to aband cas shown in figure which are unified into one case by our relabeling the trinode restructuring then replaces with the node called bmakes the children of this node be and cand makes the children of and be the four previous children of xyand (other than andywhile maintaining the inorder relationships of all the nodes in code fragment the trinode restructuring operation in binary search tree