LL Rotation
The tree shown in following figure is an AVL Tree, however, we,need to insert an element into the left of the left sub-tree of A. the tree can become unbalanced with the presence of the critical node A.
The node whose balance factor doesn’t lie between -1 and 1, is called critical node.
In order to rebalance the tree, LL rotation is performed as shown in the following diagram.
The node B becomes the root, with A and T3 as its left and right child. T1 and T2 becomes the left and right sub-trees of A.
Example :
Insert the node with value 12 into the tree shown in the following figure.
Solution:
12 will be inserted to the left of 25 and therefore, it disturbs the AVLness of the tree. The tree needs to be rebalanced by rotating it through LL rotation.
Here, the critical node 100 will be moved to its right, and the root of its left sub-tree (B) will be the new root node of the tree.
The right sub-tree of B i.e. T2 (with root node 75) will be place to the left of Node A (with value 100).
By following this procedure, the tree will be rebalanced and therefore, it will be an AVL tree produced after inserting 12 into it.
