How to balance an AVL tree

AVL trees are self-balancing binary search trees. This means that whenever an imbalanceAn imbalance in a binary search tree happens due to one subtree of a node being heavier than the other subtree. is created via the insertion or deletion of a node(s), these trees can restore the balance.

NOTE: To learn more about what an AVL tree is, and the different types of imbalances that can arise in them due to the insertion/deletion of a node(s), refer to this link.

This maintenance of balance in an AVL tree allows operations such as insertion, deletion, and searching to run in $O(log(N))$ time. This makes them much more efficient than simple binary search trees, which take $O(N)$ time in the worst case.

Balance

AVL trees can maintain this balance by keeping track of the balance factorThe balance factor of a node is the difference in the height of the left and right sub-tree. The balance factor of every node in the AVL tree should be either +1, 0 or -1. of each node. If the balance factor of a node doesn't lie in the range $[-1, 1]$ , then AVL trees can perform rotations. These rotations involve switching around positions of nodes in the unbalanced node's sub-tree(s) each time the balance factor is disrupted.

There are two categories of rotations, which each contain 2 types of rotations. Each rotation deals with a particular type of imbalance that may arise.

Single rotations

There are 2 rotations in this category:

Right rotation—to deal with the left-left imbalance.
Left rotation—to deal with the right-right imbalance.

Given an unbalanced node $x$ with children $y$ and $T_1$ , a single-rotation involves making $y$ a parent of $x$ . The diagrams below illustrate how right-rotation and left-rotation work:

Double rotations

There are 2 rotations in this category:

Right-left rotation—to deal with the right-left imbalance.
Left-right rotation—to deal with the left-right imbalance.

As the name suggests, these rotations are a combination of two single rotations applied after each other

Given an unbalanced node $x$ with children $y$ and $T_1$ , and given that $y$ is the parent of node $z$ , the first rotation involves making $z$ the parent of $y$ . Now, $z$ is a child of $x$ .
Then, the second rotation involves making $z$ the parent of $x$ as well.

The diagrams below illustrate how the left-right rotation and the right-left rotation work:

Note: Although the rebalancing of an AVL tree can happen after every insertion/deletion, here, we will build our hard-coded tree such that it only needs to happen once. The tree we will build will always be balanced until the 6th node (with $value=7$ ) is inserted.
The tree is constructed this way to demonstrate rebalancing at work, in isolation from a proper AVL tree insertion implementation.

Once the tree is built, we'll rebalance it via the balanceTree() function. The image below demonstrates the effect of this rebalancing:

#include <iostream>
using namespace std;
class Node 
{
  public:
    int value;
  Node * left_child;
  Node * right_child;
  Node() 
  {
    value = 0;
    left_child = NULL;
    right_child = NULL;
  }
  Node(int v) 
  {
    value = v;
    left_child = NULL;
    right_child = NULL;
  }
};
class AVLtree 
{
  public:
    Node * root;
  AVLtree() 
  {
    root = NULL;
  }
 
  int height(Node * r) 
  {
    if (r == NULL)
    {
      return -1;
    }
    else 
    {
      int left_subtree_height = height(r->left_child);
      int right_subtree_height = height(r->right_child);
      if (left_subtree_height > right_subtree_height)
      {
        return (left_subtree_height + 1);
      }
      else 
      {
        return (right_subtree_height + 1);
      }
    }
  }
  int getBalanceFactor(Node * n) 
  {
    if (n == NULL)
    {
      return -1;
    }
    return height(n->left_child) - height(n->right_child);
  }
  Node * rightRotate(Node * x) 
  {
    Node * y = x->left_child;
    Node * T2 = y->right_child;
    // Perform rotation  
    y->right_child = x;
    x->left_child = T2;
    return y;
  }
  Node * leftRotate(Node * x) 
  {
    Node * y = x->right_child;
    Node * T2 = y->left_child;
    // Perform rotation  
    y->left_child = x;
    x->right_child = T2;
    return y;
  }
  Node * balanceTree(int balance_factor, Node * unbalanced_node , Node * latest_inserted_node)
  {
    if (balance_factor > 1) 
    {
      // left-left imbalance
      if(getBalanceFactor(unbalanced_node->left_child) >= 0)
      {
        unbalanced_node = rightRotate(unbalanced_node);
        return unbalanced_node;
      }
      // left-right imbalance
      else if(getBalanceFactor(unbalanced_node->left_child) == -1)
      {
        unbalanced_node->left_child = leftRotate(unbalanced_node->left_child);
        unbalanced_node = rightRotate(unbalanced_node);
        return unbalanced_node;
      }
    }
    if (balance_factor < -1) 
    {
      // right-right imbalance  
      if(getBalanceFactor(unbalanced_node->right_child) <= -0)
      {
        unbalanced_node = leftRotate(unbalanced_node);
        return unbalanced_node;
      }
      // right-left imbalance 
      else if(getBalanceFactor(unbalanced_node->right_child) == 1)
      {
        unbalanced_node->right_child = rightRotate(unbalanced_node->right_child);
        unbalanced_node = leftRotate(unbalanced_node);
        return unbalanced_node;
      }
    }
  }
};
void prettyPrintTree(Node * r, int space) 
{
  if (r == NULL) 
  {
    return;
  }
  space += 10; 
  prettyPrintTree(r->right_child, space); 
  cout << endl;
  for (int i = 10; i < space; i++) 
  {
    cout << " ";   
  }
  cout << r->value << "\n"; 
  prettyPrintTree(r->left_child, space); 
}
int main()
{
  AVLtree obj;
  //Node n1;
  Node * n1 = new Node();
  //Node n2;
  Node * n2 = new Node();
  //Node n3;
  Node * n3 = new Node();
  //Node n4;
  Node * n4 = new Node();
  //Node n5;
  Node * n5 = new Node();
  //Node n6;
  Node * n6 = new Node();
  n1->value = 20;
  n2->value = 15;
  n3->value = 30;
  n4->value = 10;
  n5->value = 17;
  n6->value = 7;
  // First level (root 20):
  obj.root = n1 ;
  // Second level (root 20, left_child 15, right_child 30)
  obj.root->left_child = n2 ;
  obj.root->right_child = n3;
  // Third level (root 15, left_child 10, right_child 17): 
  obj.root->left_child->left_child = n4;
  obj.root->left_child->right_child = n5 ;
  // Fourth level (root 10, left_child 7, right_child NULL):
  obj.root->left_child->left_child->left_child = n6 ;
  // This tree is unbalanced (at the root node 20, which
  // has a balance factor of +2).
  cout << "Tree before balancing:" << endl ;
  prettyPrintTree(obj.root , 1);
  int bf = obj.getBalanceFactor(obj.root); // bf=2
  obj.root = obj.balanceTree(bf, obj.root , n6);
  cout << "\n==================================================================" << endl ;
  cout << "Tree after balancing:" << endl ;
  prettyPrintTree(obj.root , 1);
  return 0 ;
}

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

How to balance an AVL tree

Balance

Single rotations

Double rotations

Code