Common AVL rotation techniques
Before jumping into the actual techniques, it’s important to understand what balance factor is.
Balance Factor
The balance factor of a node is the difference in the heights of the left and right subtrees. The balance factor of every node in the AVL tree should be either +1, 0 or -1.
In case a node is imbalanced, a rotation technique can be applied to balance it. Some common ones are below.
Rotation Techniques
Right Rotation
A single rotation applied when a node is inserted in the left subtree of a left subtree. In the given example, node C now has a balance factor of 2 after the insertion of node A. By rotating the tree right, node B becomes the root resulting in a balanced tree.
Left Rotation
A single rotation applied when a node is inserted in the right subtree of a right subtree. In the given example, node A has a balance factor of 2 after the insertion of node C. By rotating the tree left, node B becomes the root resulting in a balanced tree.
Left-Right Rotation
A double rotation in which a left rotation is followed by a right rotation. In the given example, node B is causing an imbalance resulting in node C to have a balance factor of 2. As node B is inserted in the right subtree of node A, a left rotation needs to be applied. However, a single rotation will not give us the required results. Now, all we have to do is apply the right rotation as shown before to achieve a balanced tree.
Right-Left Rotation
A double rotation in which a right rotation is followed by a left rotation. In the given example, node B is causing an imbalance resulting in node A to have a balance factor of 2. As node B is inserted in the left subtree of node C, a right rotation needs to be applied. However, just as before, a single rotation will not give us the required results. Now, by applying the left rotation as shown before, we can achieve a balanced tree.
RELATED TAGS
