search trees in the context of tree-balancing algorithma rotation allows the shape of tree to be modified while maintaining the search tree property if used wiselythis operation can be performed to avoid highly unbalanced tree configurations for examplea rightward rotation from the first formation of figure to the second reduces the depth of each node in subtree by onewhile increasing the depth of each node in subtree by one (note that the depth of nodes in subtree are unaffected by the rotation one or more rotations can be combined to provide broader rebalancing within tree one such compound operation we consider is trinode restructuring for this manipulationwe consider position xits parent yand its grandparent the goal is to restructure the subtree rooted at in order to reduce the overall path length to and its subtrees pseudo-code for restructure(xmethod is given in code fragment and illustrated in figure in describing trinode restructuringwe temporarily rename the positions xyand as aband cso that precedes and precedes in an inorder traversal of there are four possible orientations mapping xyand to aband cas shown in figure which are unified into one case by our relabeling the trinode restructuring replaces with the node identified as bmakes the children of this node be and cand makes the children of and be the four previous children of xyand (other than and )while maintaining the inorder relationships of all the nodes in algorithm restructure( )inputa position of binary search tree that has both parent and grandparent outputtree after trinode restructuring (which corresponds to single or double rotationinvolving positions xyand let (abcbe left-to-right (inorderlisting of the positions xyand zand let ( be left-to-right (inorderlisting of the four subtrees of xyand not rooted at xyor replace the subtree rooted at with new subtree rooted at let be the left child of and let and be the left and right subtrees of arespectively let be the right child of and let and be the left and right subtrees of crespectively code fragment the trinode restructuring operation in binary search tree in practicethe modification of tree caused by trinode restructuring operation can be implemented through case analysis either as single rotation (as in figure and bor as double rotation (as in figure and dthe double rotation arises when position has the middle of the three relevant keys and is first rotated above its parentand then above what was originally its grandparent in any of the casesthe trinode restructuring is completed with ( running time