performing local trinode restructurings (rotationsjava implementation let us now turn to the implementation details and analysis of using an avl tree with internal nodes to implement an ordered dictionary of entries the insertion and removal algorithms for require that we are able to perform trinode restructurings and determine the difference between the heights of two sibling nodes regarding restructuringswe now need to make sure our underlying implementation of binary search tree includes the method restructure( )which performs tri-node restructuring operation (code fragment it is easy to see that restructure operation can be performed in ( time if is implemented with linked structure (section in our casewe assume that the binarysearchtree class includes this method regarding height informationwe can explicitly store the height of each internal nodevin the node itself alternativelywe can store the balance factor of at vwhich is defined as the height of the left child of minus the height of the right child of thusthe balance factor of is always equal to - or except during an insertion or removalwhen it may become temporarily equal to - or + during the execution of an insertion or removalthe heights and balance factors of (lognnodes are affected and can be maintained in (logntime