( (bfigure an example insertion of an item with key in the avl tree of figure (aafter adding new node for key the nodes storing keys and become unbalanced(ba trinode restructuring restores the height-balance property we show the heights of nodes above themand we identify the nodes xyand and subtrees and participating in the trinode restructuring we restore the balance of the nodes in the binary search tree by simple "search-and-repairstrategy in particularlet be the first position 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 must be an ancestor of pfinallylet be the child of with higher height (there cannot be tie and position must also be an ancestor of ppossibly itself we rebalance the subtree rooted at by calling the trinode restructuring methodrestructure( )originally described in section an example of such restructuring in the context of an avl insertion is portrayed in figure to formally argue the correctness of this process in reestablishing the avl height-balance propertywe consider the implication of being the nearest ancestor of that became unbalanced after the insertion of it must be that the height of increased by one due to the insertion and that it is now greater than its sibling since remains balancedit must be that it formerly had subtrees with equal heightsand that the subtree containing has increased its height by one that subtree increased either because pand thus its height changed from to or because previously had equal-height subtrees and the height of the one containing has increased by letting > denote the height of the tallest child of xthis scenario might be portrayed as in figure after the trinode restructuringwe see that each of xyand has become balanced furthermorethe node that becomes the root of the subtree after the restructuring has height which is precisely the height that had before the insertion of the new item thereforeany ancestor of that became temporarily unbalanced becomes balanced againand this one restructuring restores the heightbalance property globally