finallywe will insert to show the symmetric case of the double rotation notice that causes the node containing to become unbalanced since is between and (which is ' child on the path to ) double rotation needs to be performedyielding the following tree after let us summarize what happens the programming details are fairly straightforward except that there are several cases to insert new node with item into an avl tree twe recursively insert into the appropriate subtree of (let us call this tlr if the height of tlr does not changethen we are done otherwiseif height imbalance appears in twe do the appropriate single or double rotation depending on and the items in and tlr update the heights (making the connection from the rest of the tree above)and we are done since one rotation always sufficesa carefully coded nonrecursive version generally turns out to be faster than the recursive versionbut on modern compilers the difference is not as significant as in the past howevernonrecursive versions are quite difficult to code correctlywhereas casual recursive implementation is easily readable another efficiency issue concerns storage of the height information since all that is really required is the difference in heightwhich is guaranteed to be smallwe could get by with two bits (to represent + - if we really try doing so will avoid repetitive calculation of balance factors but results in some loss of clarity the resulting code is somewhat more complicated than if the height were stored at each node if recursive routine is writtenthen speed is probably not the main consideration in this casethe slight speed advantage obtained by storing balance factors hardly seems worth the loss of clarity and relative simplicity furthermoresince most machines will align this to at least an -bit boundary anywaythere is not likely to be any difference in the amount of space used an -bit (signedchar will allow us to store absolute heights of up to since the tree is balancedit is inconceivable that this would be insufficient (see the exercises