< + key key before after < + - or - key key before or key - or key after figure cases (topand (bottomare mirror images of cases and its left child or it has right high balance and the new node is inserted into its right childthe node is out of balance and its subtree has to be rebalanced after rebalancingthe subtree will shrink by one levelwhich results in the balance factors of its ancestors remaining the same the balance factors of the ancestors will also remain the same when the balance factor changes to equal high after rotation is performedthe balance factor of the impacted nodes have to be changed to reflect the new node heights the changes required depend on which of the four cases triggered the rotation the balance factor settings in cases and depend on the balance factor of the original pivot nodes grandchild (the right child of node or the left child of node rthe new balance factors for the nodes involved in rotation are provided in table figure illustrates the construction of an avl tree by inserting the keys from the list [ ]one key at time each tree in the figure shows the results after performing the indicate operation two double rotations are required to construct the treeone after node is inserted and one after node is inserted deletions when an entry is removed from an avl treewe must ensure the balance property is maintained as with the insert operationdeletion begins by using the corre