AVL

This page provides links to solutions that use the AVL.

Overview

An AVL tree is a self-balancing binary search tree. It was one of the first data structures designed to maintain balance in a binary search tree, ensuring that the height difference between the left and right subtrees of any node is limited to at most one.

This balancing property helps maintain efficient search, insertion, and deletion operations, as the worst-case height of the tree remains $\text{O(log n)}$ .

AVL trees require more rotations compared to other self-balancing trees like Red-Black trees. This can make AVL trees slightly slower in practice, especially when performing a lot of insertions and deletions.

How to Build AVL Tree

Let's start by defining tree node and functions needed for AVL tree generation:

Java

class TreeNode {
  int key = 0;
  int height = 1;
  TreeNode left, right;

  public TreeNode(int key, TreeNode left, TreeNode right, int height){
    this.key = key;
    this.left = left;
    this.right = right;
    this.height = height;
  }

  public TreeNode(int key) {
    this.key = key;
  }
}

Now, let's define function to get height and balance of a tree as below:

Java

public int height(TreeNode root) {
  if(root != null) return root.height;
  else return 0;
}

public int balance(TreeNode root) {
  if(root != null) return height(root.left) - height(root.right);
  else return 0;
}

If the balance of an AVL tree is off, meaning the height difference between the left and right subtrees of any node exceeds $1$ , rotations are required to restore balance. Let's begin by understanding the AVL rotation function.

Rotate Left Function

Java

/**
 * It is easier to learn this function from the diagram below
 * 
 * Input:
 *    1
 *      3
 *    2
 * 
 * Output:
 *    3
 *  1
 *    2
**/
public TreeNode rotateLeft(TreeNode root) {
  // 1. right node becomes new root node and 
  TreeNode newRoot = root.right;

  // 2. whatever is on the left of new root node is assigned to temporary variable
  TreeNode temp = newRoot.left; 

  // 3. old root goes to left of new root
  newRoot.left = root; 

  // 4. temp variable from step 2 is assigned to right of old root
  root.right = temp;

  // 5. update height variables for old and new root node
  newRoot.height = 1 + Math.max(height(newRoot.left), height(newRoot.right));
  root.height = 1 + Math.max(height(root.left), height(root.right));

  return newRoot;
} 

Rotate Right Function

Java

/**
 * It is easier to learn this function from the diagram below
 * 
 * Input:
 *     3
 *   1   
 *     2
 * 
 * Output:
 *     1
 *       3
 *     2
**/
public TreeNode rotateRight(TreeNode root) {
  // 1. left node becomes new root node and 
  TreeNode newRoot = root.left;

  // 2. whatever is on the right of new root node is assigned to temporary variable
  TreeNode temp = newRoot.right; 

  // 3. old root goes to right of new root
  newRoot.right = root; 

  // 4. temp variable from step 2 is assigned to left of old root
  root.left = temp;

  // 5. update height variables for old and new root node
  newRoot.height = 1 + Math.max(height(newRoot.left), height(newRoot.right));
  root.height = 1 + Math.max(height(root.left), height(root.right));

  return newRoot;
} 

Let's build a AVL tree for the array below:

\text{arr} = \begin{bmatrix} \text{30, 20, 10, 40, 50, 25, 35} \end{bmatrix}

Tree is balanced after adding $30$ to AVL tree. No rotations are required.

Tree is balanced after adding $20$ to AVL tree. No rotations are required.

Case LL

Adding $10$ to the AVL tree causes it to become unbalanced. This is an LL case at node $30$ because it is the first node with a balance factor greater than $1$ encountered during backtracking.

Here’s how it happens:

After inserting node $10$ , we calculate its balance, which is within the acceptable threshold.
Moving up to the parent node $20$ , we recalculate its balance, which also remains within the threshold.
Finally, we backtrack to the parent node $30$ and find that its balance exceeds the threshold, indicating that a rotation is required to restore balance in the AVL tree.

Since the balance at node $30$ is greater than $1$ , we know the imbalance is in its left subtree. Further checking reveals that the new node $10$ is less than the left child of node $30$ , confirming this is an LL case.

To restore balance, a right rotation will be performed on the unbalanced node $30$ .

Java

if(balance > 1 && key < root.left.key) return rotateRight(root);

Tree is balanced adding $40$ to AVL tree. No rotations are required.

Case RR

Similarly, adding $50$ to the AVL tree causes it to become unbalanced. This is an RR case at node $30$ because it is the first node with a balance factor less than $-1$ encountered during backtracking.

To restore balance, a left rotation will be performed on the unbalanced node $30$

Java

if(balance < -1 && key > root.right.key) return rotateLeft(root);

Case RL

Adding $25$ to the AVL tree causes it to become unbalanced. This is an RL case because the new element is added to the right child of node $20$ within its left subtree, creating an imbalance with more elements on the right subtree of node $20$ .

To restore balance in the AVL tree:

A right rotation is applied to node $40$ .
This is followed by a left rotation on node $20$ .

Java

if(balance < -1 && key < root.right.key) {
  root.right = rotateRight(root.right);
  return rotateLeft(root);
}

Case LR

Similarly there will be a case, where key will be added to the left child of the node within its the right subtree, creating a imbalance with more elements on the left subtree.

To restore balance in the AVL tree:

A left rotation is applied to the left child of the right subtree.
This is followed by a right rotation on the imbalanced node.

Java

public TreeNode insert(TreeNode root, int key) {
  if(root == null) {
    return new TreeNode(key);
  }

  if(key < root.key) {
    root.left = insert(root.left, key);
  }
  else if(key > root.key) {
    root.right = insert(root.right, key);
  }
  else return root;

  // update height
  root.height = 1 + Math.max(height(root.left), height(root.right));

  // get balance 
  balance = balance(root);

  // case LL
  if(balance > 1 && key < root.left.key) return rotateRight(root);

  // case RR
  if(balance < -1 && key > root.right.key) return rotateLeft(root);
  
  // case RL
  if(balance < -1 && key < root.right.key) {
    root.right = rotateRight(root.right);
    return rotateLeft(root);
  }

  // case LR
  if(balance > 1 && key > root.left.key) {
    root.left = rotateLeft(root.left);
    return rotateRight(root);
  }
  
  return root;
}

How to Use AVL Tree

You can use the AVL tree to search for an element in $\text{O}(\text{log N})$ time.

Java

public TreeNode search(TreeNode root, int key) {
  if(root == null) return root;
  if(key < root.key) return search(root.left, key);
  else if(key > root.key) return search(root.right, key);
  else return root;
}

How to Update AVL Tree

To update a node in a binary search tree, we first delete the existing node and then add a new node to the tree.

Let's begin by defining the delete operation, there are four cases to consider for node deletion:

A node has no left child.
A node has no right child.
A node has no children.
A node has both left and right children.

The first three cases are straightforward because the node to be deleted can simply be replaced with its existing child or set to null if it has no children.

For the fourth case, we need to find the node's inorder predecessor (the largest node in it's left subtree) and replace the node to be deleted with its inorder predecessor.

After deleting an element from the AVL tree, check if the tree has become unbalanced and determine the type of imbalance.

If the balance factor > $1$ , it indicates that the left subtree is taller than the right subtree and exceeds the allowable threshold. To determine the specific scenario, check the balance factor of the left child of the node. There are two possibilities:

Case LL: The left subtree of the left child is heavier.

Case LR: The right subtree of the left child is heavier.

If the balance factor < $1$ , it indicates that the right subtree is taller than the left subtree and exceeds the allowable threshold. To determine the specific scenario, check the balance factor of the right child of the node. There are two possibilities:

Case RR: The right subtree of the right child is heavier.

Case RL: The left subtree of the right child is heavier.

Java

private TreeNode inorderPredecessor(TreeNode root) {
  while(root.left != null) root = root.left;
  return root;
}

public TreeNode delete(TreeNode root, int key) {
  if(root == null) return root;

  if(key < root.key) {
    root.left = delete(root.left, key);
  }
  else if(key > root.key) {
    root.right = delete(root.right, key);
  }
  else {
    if(root.left == null && root.right == null) return null;
    else if(root.left == null) return root.right;
    else if(root.right == null) return root.left;
    else {
      TreeNode replaceNode = inorderPredecessor(root.right);
      root.key = replaceNode.key;
      root.right = delete(root, replaceNode.key);
    }
  }

  // update height
  root.height = 1 + Math.max(height(root.left), height(root.right));

  // balance 
  balance = balance(root);

  // case LL
  if(balance > 1 && balance(root.left) >= 0) {
    return rotateRight(root);
  }

  // case LR
  if(balance > 1 && balance(root.left) < 0) {
    root.left = rotateLeft(root.left);
    return rotateRight(root);
  }

  // case RR 
  if(balance < -1 && balance(root.right) <= 0) {
    return rotateLeft(root);
  }

  // case RL
  if(balance < -1 && balance(root.right) > 0) {
    root.right = rotateRight(root.right);
    return rotateLeft(root);
  }

  return root;
}

Now, update operation will look like below:

Java

public TreeNode update(TreeNode root, int oldKey, int newKey) {
  delete(root, oldKey);
  insert(root, newKey);
  return root;
}

How to Spot These Problems

You can identify AVL tree problems if the problem requires you to:

Ensuring the tree remains balanced after insertions or deletions.
Performing search, insertion, or deletion in $\text{O}(\text{log N})$ time.

Overview​

How to Build AVL Tree​

Rotate Left Function​

Rotate Right Function​

Case LL​

Case RR​

Case RL​

Case LR​

How to Use AVL Tree​

How to Update AVL Tree​

How to Spot These Problems​

Leetcode Problem Set​