Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

avl
data structures

Common AVL rotation techniques

Educative Answers Team

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.

svg viewer
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

svg viewer

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.

svg viewer

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.