data structures using - - - - - - figure avl tree figure avl tree after inserting node with the value figure avl tree let us take another example to see how insertion can disturb the balance factors of the nodes and how rotations are done to restore the avl property of tree look at the tree given in fig after inserting new node with the value the new tree - will be as shown in fig note that there are three nodes in the tree that have their balance factors - and - thereby - disturbing the avlness of the tree sohere comes the need to perform rotation to perform rotationour first task is to find the critical node critical node is the nearest ancestor node on the path from the inserted node to the root whose balance factor is neither - - nor in the tree given abovethe critical node is the second task in rebalancing the tree is to determine which type of rotation has to be done there are four types of rebalancing figure avl tree after inserting rotations and application of these rotations depends on the position node with the value of the inserted node with reference to the critical node the four categories of rotations arell rotation the new node is inserted in the left sub-tree of the left sub-tree of the critical node rr rotation the new node is inserted in the right sub-tree of the right sub-tree of the critical node lr rotation the new node is inserted in the right sub-tree of the left sub-tree of the critical node rl rotation the new node is inserted in the left sub-tree of the right sub-tree of the critical node ll rotation let us study each of these rotations in detail firstwe will see where and how ll rotation is applied consider the tree given in fig ( ( ( + which shows an avl tree tree (ais an avl tree in tree ( ) new ( ( ( ( ( (hnode is inserted in the left sub-tree of the left height + sub-tree of the critical node (node is the new node critical node because it is the closest ancestor ( ( (cwhose balance factor is not - or )so figure ll rotation in an avl tree we apply ll rotation as shown in tree (cnote the new node has now become part of tree