How to Balance an AVL Tree (Cheatsheet)

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.
A left-left heavy tree
A left-left heavy tree

LEFT-RIGHT Heavy Tree

  • The right sub-tree of the left child grew.
  • To balance: Left rotation around child, then right rotation around root.
Left-Right Heavy
A left-right heavy tree.

RIGHT-RIGHT Heavy Tree

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

RIGHT-LEFT Heavy Tree

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

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 child node for the first rotation, and the original root node for the second rotation.

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

Angus Macdonald

Angus works in New York City for Google. He has a PhD in Computer Science from the University of St Andrews.

Latest posts by Angus Macdonald (see all)

Leave a Reply

Your email address will not be published. Required fields are marked *