search trees insertions inserting key into an avl tree begins with the same process used with binary search tree we search for the new key in the tree and add new node at the child link where we fall off the tree when new key is inserted into an avl treethe balance property of the tree must be maintained if the insertion of the new key causes any of the subtrees to become unbalancedthey will have to be rebalanced some insertions are simpler than others for examplesuppose we want to add key to the sample avl tree from figure (afollowing the insertion operation of the binary search treethe new key will be inserted as the right child of node as illustrated in figure (athe tree remains balanced since the insertion does not change the height of any subtreebut it does cause change in the balance factors after the key is insertedthe balance factors have to be adjusted in order to determine if any subtree is out of balance there is limited set of nodes that can be affected when new key is added this set is limited to the nodes along the path to the insertion point figure (bshows the new balance factors after key is added ( ( figure simple insertion into an avl tree(awith key insertedand (bthe new balance factors what happens if we add key to the avlthe new node is inserted as the left child of node as illustrated in figure (awhen the balance factors are recalculatedas in figure ( )we can see all of the subtrees along the path that are above node are now out of balancewhich violates the avl balance property for this examplewe can correct the imbalance by rearranging the subtree rooted at node as illustrated in figure (crotations multiple subtrees can become unbalanced after inserting new keyall of which have roots along the insertion path but only one will have to be rebalancedthe one deepest in the tree and closest to the new node after inserting the keythe balance factors are adjusted during the unwinding of the recursion the first