Struggling to remember how to balance an AVL tree? I created this cheatsheet as a study aid when I was a tutor at the University of St Andrews as a quick reference guide.

## Terminology

The * root node* is the first node above the inserted node that is unbalanced.

The * child node* is either the left or right child of the root node. The child node involved in rotation is the node on the path towards the recently inserted value.

## Which Operations to Perform

**LEFT-LEFT** Heavy Tree

*The left sub-tree of the left child grew.*- To balance: Right rotation around the root.

**LEFT-RIGHT** Heavy Tree

*The right sub-tree of the left child grew.*- To balance: Left rotation around child,
*then r*ight rotation around root.

**RIGHT-RIGHT **Heavy Tree

*The right sub-tree of the right child grew.*- To balance: Left rotation around root.

**RIGHT-LEFT** Heavy Tree

*The left sub-tree of the right child grew.*- To balance: right rotation around child,
*then*left rotation around root.

## Rotation Algorithm

In the case of single right and left rotations the * pivot* is the

*.*

**root node**In the case of left-right and right-left rotations the * pivot* is the

*for the first rotation, and the original*

**child node***for the second rotation.*

**root node**### Rotating Right

1. Save value of pivot.left (temp = pivot.left)

2. Set pivot.left to value of pivot.left.right

3. Set temp.right to pivot

4. Set pivot to temp

### Rotating Left

1. Save value of pivot.right (temp = pivot. right)

2. Set root. right to value of pivot.right.left

3. Set temp.left to pivot

4. Set pivot to temp