search treesbut with avl trees we must perform additional computations insertion an insertion in an avl tree begins as in an insert operation described in section for (simplebinary search tree recall that this operation always inserts the new entry at node in that was previously an external nodeand it makes become an internal node with operation insertatexternal that isit adds two external node children to this action may violate the heightbalance propertyhoweverfor some nodes increase their heights by one in particularnode wand possibly some of its ancestorsincrease their heights by one thereforelet us describe how to restructure to restore its height balance given binary search tree twe say that an internal node of is balanced if the absolute value of the difference between the heights of the children of is at most and we say that it is unbalanced otherwise thusthe height-balance property characterizing avl trees is equivalent to saying that every internal node is balanced suppose that satisfies the height-balance propertyand hence is an avl treeprior to our inserting the new entry as we have mentionedafter performing the operation insertatexternal on tthe heights of some nodes of tincluding wincrease all such nodes are on the path of from to the root of tand these are the only nodes of that may have just become unbalanced (see figure of courseif this happensthen is no longer an avl treehencewe need mechanism to fix the "unbalancethat we have just caused figure an example insertion of an entry 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 next to themand we identify the nodes xyand participating in the trinode restructuring