chap advanced tree structures figure example of an insert operation that violates the avl tree balance property prior to the insert operationall nodes of the tree are balanced ( the depths of the left and right subtrees for every node differ by at most oneafter inserting the node with value the nodes with values and are no longer balanced ( (bc figure single rotation in an avl tree this operation occurs when the excess node (in subtree ais in the left child of the left child of the unbalanced node labeled by rearranging the nodes as shownwe preserve the bst propertyas well as re-balance the tree to preserve the avl tree balance property the case where the excess node is in the right child of the right child of the unbalanced node is handled in the same way our problem now is how to balance the tree in (log ntime it turns out that we can do this using series of local operations known as rotations cases and can be fixed using single rotationas shown in figure cases and can be fixed using double rotationas shown in figure the avl tree insert algorithm begins with normal bst insert then as the recursion unwinds up the treewe perform the appropriate rotation on any node that is