trees struct avlnode comparable elementavlnode *leftavlnode *rightint heightavlnodeconst comparable eleavlnode *ltavlnode *rtint elementele }leftlt }rightrt }heighth avlnodecomparable &eleavlnode *ltavlnode *rtint elementstd::moveele }leftlt }rightrt }heighth }figure node declaration for avl trees /*return the height of node or - if nullptr *int heightavlnode * const return =nullptr - ->heightfigure function to compute height of an avl node with all thiswe are ready to write the avl routines we show some of the code herethe rest is online firstwe need the avlnode class this is given in figure we also need quick function to return the height of node this function is necessary to handle the annoying case of nullptr pointer this is shown in figure the basic insertion routine (see figure adds only single line at the end that invokes balancing method the balancing method applies single or double rotation if neededupdates the heightand returns the resulting tree for the trees in figure rotatewithleftchild converts the tree on the left to the tree on the rightreturning pointer to the new root rotatewithrightchild is symmetric the code is shown in figure similarlythe double rotation pictured in figure can be implemented by the code shown in figure since deletion in binary search tree is somewhat more complicated than insertionone can assume that deletion in an avl tree is also more complicated in perfect worldone would hope that the deletion routine in figure could easily be modified by changing the last line to return after calling the balance methodas was done for insertion this would yield the code in figure this change worksa deletion could cause one side