Related Tags

avl
data structures

# 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.

Examples of Nodes with Different Balance Factors

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.