Binary Search Trees: AVL Trees

5 min readDec 29, 2022

Digging into AVL trees

An AVL tree is a type of self-balanced binary tree. It is named after its authors: Adelson-Velsky and Landis. In an AVL tree, for each node, the difference in height between the left and right subtree cannot be more than one.

To ensure that, it verifies after each addition that the tree is still balanced. If not, more operations are done. Those operations are called rotations.

Left Rotation

A left rotation on a node N is described like this:

Take the right child of N, we name it Y
Take the left child of Y, name it Z

Replace the left child of Y by N

Replace the right child of N by Z

As a pseudo-code, it would look like this:

function rotate_left(node: TreeNode)
  let y = node.right
  let z = y.left
  y.left = node
  node.right = z
  node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))
  y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
  return y

Right Rotation

A right rotation follows the same principle:

Take the left child of N, we name it Y
Take the right child of Y, name it Z
Replace the right child of Y by N
Replace the left child of N by Z

function rotate_right(node: TreeNode)
  let y = node.left
  let z = y.right
  y.right = node
  node.left = z
  node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))
  y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
  return y

Knowing what operation(s) to execute

After each insertion, we check if the tree is still balanced. If it is not, we find the first node above the inserted node that is unbalanced.

Let’s call the inserted node N and the unbalanced node U.

We first check the balance factor of U. To do that, we calculate the difference in height between its left and right subtree.

Let’s call that height difference D.

Then if D > 1, it means the left subtree is longer than the right subtree, the unbalance is on the left side. Intuitively, we can think that we have to do a rotation to the right. But that’s not that simple. We can be in two cases: a ‘left left’ case, where we’ll only have to perform a right rotation, or a ‘left right’ case, where we first have to perform a left rotation and then a right rotation.

The same goes with D < -1.

Dealing with the left cases

In the Left cases, we know that the unbalance is on the left side of the tree.

Let’s call C the left child of U.

Left Left case

When the value of C is greater than N's, it means N will be in the left subtree of C. We call this the ‘left left case’. It means, starting from the unbalanced node U, you have to take the left child and then the left child again to be on the correct path towards N.

In the Left Left case, the unbalance is entirely located on the left side of the tree. So it can be repaired by doing a right rotation on the unbalanced node U.

Left Right case

When the value of C is smaller than that of N, it means N will be in the right subtree of C. We call this the ‘left-right case’. It means, starting from the unbalanced node U, you have to take the left child and then the right child to be on the correct path towards N.

In the Left Right case, the unbalance is located on the left side of the tree, but on the right subtree of C. Before fixing the unbalance, we need to rotate the tree on C to the left, so the unbalance goes back on the Left Left case.

Once done, we can perform a right rotation on U and get our tree balanced again.

Dealing with the Right cases

In the Right cases, we know the unbalance is on the right side of the tree.

Let’s call C the right child of U.

Right Right case

When the value of C is lower than that of N, N will be in the right subtree of C. We call this the ‘right right case’. It means, starting from the unbalanced node U, you have to take the right child and then the right child again to be on the correct path towards N.

In the Right Right case, the unbalance is entirely located on the right side of the tree. So it can be repaired by doing a left rotation on the unbalanced node U.

Right Left case

Similarly, in a right left case, C is greater than N, so the unbalanced is first on the right, then on the left.

It means we first need to do a Right rotation on C, then a left rotation on U to fix the unbalance.

In code

To do this in code, it would look like this:

function get_height(node:TreeNode)
  if node == null
    return 0
  endif
  return node.height


function get_balance(node: TreeNode, value: int)
  if node == null
    return 0
  endif
  return get_height(node.left) - get_height(node.right)

function rebalance(node: TreeNode)
  let balance = get_balance(node)
  if balance > 1                 // we are in the left cases
    if value < node.left.value   // we are in the left left case
      return rotate_right(node)
    else                         // we are in the left right case
      node.left = rotate_left(node.left)
      return rotate_right(node)
    endif
  endif

  if balance <-1                 // we are in the right cases
    if value > node.right.value  // we are in the right right case
      return rotate_left(node)
    else                         // we are in the right left case
      node.right = rotate_right(node.right)
      return rotate_left(node)
    endif
  endif
  return node                    // any other cases

function insert(node: TreeNode, value: int)
  if node == null
    return new TreeNode(value)
  else if value < node.value
    node.left = insert(node.left, value)
  else
    node.right = insert(node.right, value)
  endif

  node.height = 1 + max(get_height(node.left), get_height(node.right))
  return rebalance(node, value)

That’s it for the AVL tree, thanks for reading, see you in the next one!