sub-tree with height whereas the height of right sub-tree thusits balance factor similarlythe balance factor of node = and node has balance factor of ( nowlook at figs (aand (bwhich show right-heavy avl tree and balanced avl tree - - ( ( (cfigure (aleft-heavy avl tree(bright-heavy tree(cbalanced tree the trees given in fig are typical candidates of avl trees because the balancing factor of every node is either or - howeverinsertions and deletions from an avl tree may disturb the balance factor of the nodes andthusrebalancing of the tree may have to be done the tree is rebalanced by performing rotation at the critical node there are four types of rotationsll rotationrr rotationlr rotationand rl rotation the type of rotation that has to be done will vary depending on the particular situation in the following sectionwe will discuss insertiondeletionsearchingand rotations in avl trees operations on avl trees searching for node in an avl tree searching in an avl tree is performed exactly the same way as it is performed in binary search tree due to the height-balancing of the treethe search operation takes (log ntime to complete since the operation does not modify the structure of the treeno special provisions are required inserting new node in an avl tree insertion in an avl tree is also done in the same way as it is done in binary search tree in the avl treethe new node is always inserted as the leaf node but the step of insertion is usually followed by an additional step of rotation rotation is done to restore the balance of the tree howeverif insertion of the new node does not disturb the balance factorthat isif the balance factor of every node is still - or then rotations are not required during insertionthe new node is inserted as the leaf nodeso it will always have balance factor equal to zero the only nodes whose balance factors will change are those which lie in the path between the root of the tree and the newly inserted node the possible changes which may take place in any node on the path are as followsinitiallythe node was either leftor right-heavy and after insertionit becomes balanced initiallythe node was balanced and after insertionit becomes either leftor right-heavy initiallythe node was heavy (either left or rightand the new node has been inserted in the heavy sub-treethereby creating an unbalanced sub-tree such node is said to be critical node consider the avl tree given in fig if we insert new node with the value then the new tree will still be balanced and no rotations will be required in this case look at the tree given in fig which shows the tree after inserting node