AVL Tree in Data Structure

AVL tree is a specific type of binary search tree where the difference between heights of left and right subtrees is either 0 or 1 only for all nodes. It implements all properties of the binary search tree.

AVL tree was invented by gm Adelson – Velsky and Em Landis in 1962 and was named AVL in their honor.

Balanced binary tree

A binary tree is said to be balanced if the balance factor of each node is -1, 0, or 1. If the balance factor is any value other than these values, the tree is said to be unbalanced and needs correction.

The balance factor is the difference between the height of the right subtree and the left subtree.

Balance factor (k) = height (left(k)) – height (right(k))

• If the balance factor is 1, the left sub-tree is one level higher than the right sub-tree.
• If the balance factor is 0, the left sub-tree and right sub-tree contain equal height.
• If the balance factor is -1, the left sub-tree is one level lower than the right sub-tree.

The tree above has the properties of the binary search tree and also the balance factor for each node is either 1,0, or -1. Therefore, the above tree can be classified as an AVL tree.

Operations on AVL trees

There are 2 major operations performed on AVL trees.

• Insertion: inserting a new node in the tree
• Deletion: deleting an existing node in the tree

Insertion and deletion procedures in the AVL tree are exactly the same as the insertion and deletion procedures in the binary search tree article since the AVL tree is also a BST. But this insertion and deletion operation, after implementation can violate the AVL property of the balance factor.

To restore the balance factor within the range of -1 and 1, rotations are applied. A tree can be balanced by applying rotations.

AVL rotations

There are 4 types of rotations in AVL tree

1. L L rotation
2. R R rotation
3. R L rotation
4. L R rotation

L L rotation

If BST becomes unbalanced, due to a node being inserted into the left subtree of the left subtree of the root node, then we apply L L rotation. L L rotation is clockwise rotation and is applied on the edge below a node having balance factor 2.

R R rotation

If BST becomes unbalanced, due to a node being inserted into the right subtree of the right subtree of the root node, then we apply R R rotation. R R rotation is counter-clockwise rotation and is applied on the edge below a node having balance factor 2.

L R rotation

Double rotations are a combination of single rotations.

L R rotation = R R rotation + L L rotation

First R R rotation is performed on subtree and then L L rotation is performed on full tree.

R L rotation

R L rotation = L L rotation + R R rotation

First L L rotation is performed on subtree and then R R rotation is performed on full tree.

Working of AVL tree

Step 1: insert 78

Step 2: insert 36

Step 3: insert 120

Step 4: insert 100

Step 5: insert 110

Step 6: insert 130

Step 7: insert 50

Step 8: delete 120

Implementation of AVL Tree in C

#include <stdio.h>
#include <stdlib.h>

struct Node 
{
  int Val;
  struct Node *left;
  struct Node *right;
  int height;
};

int max(int a, int b);

int height(struct Node *N) 
{
  if (N == NULL)
    return 0;
  return N->height;
}

int max(int a, int b) 
{
  return (a > b) ? a : b;
}

struct Node *newNode(int Val) 
{
  struct Node *node = (struct Node *)
    malloc(sizeof(struct Node));
  node->Val = Val;
  node->left = NULL;
  node->right = NULL;
  node->height = 1;
  return (node);
}

struct Node *RotateRight(struct Node *y) 
{
  struct Node *x = y->left;
  struct Node *TEMP2 = x->right;

  x->right = y;
  y->left = TEMP2;

  y->height = max(height(y->left), height(y->right)) + 1;
  x->height = max(height(x->left), height(x->right)) + 1;

  return x;
}

struct Node *RotateLeft(struct Node *x) 
{
  struct Node *y = x->right;
  struct Node *TEMP2 = y->left;

  y->left = x;
  x->right = TEMP2;

  x->height = max(height(x->left), height(x->right)) + 1;
  y->height = max(height(y->left), height(y->right)) + 1;

  return y;
}

int getBalance(struct Node *N) 
{
  if (N == NULL)
    return 0;
  return height(N->left) - height(N->right);
}

struct Node *insertNode(struct Node *node, int Val) 
{
    
  if (node == NULL)
    return (newNode(Val));

  if (Val < node->Val)
    node->left = insertNode(node->left, Val);
  else if (Val > node->Val)
    node->right = insertNode(node->right, Val);
  else
    return node;

  node->height = 1 + max(height(node->left),height(node->right));

  int balance = getBalance(node);
  if (balance > 1 && Val < node->left->Val)
    return RotateRight(node);

  if (balance < -1 && Val > node->right->Val)
    return RotateLeft(node);

  if (balance > 1 && Val > node->left->Val) 
  {
    node->left = RotateLeft(node->left);
    return RotateRight(node);
  }

  if (balance < -1 && Val < node->right->Val) 
  {
    node->right = RotateRight(node->right);
    return RotateLeft(node);
  }

  return node;
}

struct Node *minValueNode(struct Node *node) 
{
  struct Node *current = node;

  while (current->left != NULL)
    current = current->left;

  return current;
}

struct Node *deleteNode(struct Node *root, int Val) 
{
  if (root == NULL)
    return root;

  if (Val < root->Val)
    root->left = deleteNode(root->left, Val);

  else if (Val > root->Val)
    root->right = deleteNode(root->right, Val);

  else 
  {
    if ((root->left == NULL) || (root->right == NULL)) 
    {
      struct Node *temp = root->left ? root->left : root->right;

      if (temp == NULL)
      {
        temp = root;
        root = NULL;
      } 
      else
        *root = *temp;
      free(temp);
    } 
    else 
    {
      struct Node *temp = minValueNode(root->right);

      root->Val = temp->Val;

      root->right = deleteNode(root->right, temp->Val);
    }
  }

  if (root == NULL)
    return root;

  root->height = 1 + max(height(root->left),height(root->right));

  int balance = getBalance(root);
  if (balance > 1 && getBalance(root->left) >= 0)
    return RotateRight(root);

  if (balance > 1 && getBalance(root->left) < 0) 
  {
    root->left = RotateLeft(root->left);
    return RotateRight(root);
  }

  if (balance < -1 && getBalance(root->right) <= 0)
    return RotateLeft(root);

  if (balance < -1 && getBalance(root->right) > 0) 
  {
    root->right = RotateRight(root->right);
    return RotateLeft(root);
  }

  return root;
}

void printPreOrder(struct Node *root) 
{
  if (root != NULL) 
  {
    printf("%d ", root->Val);
    printPreOrder(root->left);
    printPreOrder(root->right);
  }
}

int main() 
{
  struct Node *root = NULL;

  root = insertNode(root, 56);
  root = insertNode(root, 14);
  root = insertNode(root, 86);
  root = insertNode(root, 25);
  root = insertNode(root, 38);
  root = insertNode(root, 69);
  root = insertNode(root, 89);

  printPreOrder(root);

  root = deleteNode(root, 14);

  printf("AVL after deletion: ");
  printPreOrder(root);

  return 0;
}

AVL Tree implementation in C++

#include <iostream>
using namespace std;

struct Node 
{
  int Val;
  struct Node *left;
  struct Node *right;
  int height;
};

int max(int a, int b);

int height(struct Node *N) 
{
  if (N == NULL)
    return 0;
  return N->height;
}

int max(int a, int b) 
{
  return (a > b) ? a : b;
}

struct Node *newNode(int Val) 
{
  struct Node *node = (struct Node *)
    malloc(sizeof(struct Node));
  node->Val = Val;
  node->left = NULL;
  node->right = NULL;
  node->height = 1;
  return (node);
}

struct Node *RotateRight(struct Node *y) 
{
  struct Node *x = y->left;
  struct Node *TEMP2 = x->right;

  x->right = y;
  y->left = TEMP2;

  y->height = max(height(y->left), height(y->right)) + 1;
  x->height = max(height(x->left), height(x->right)) + 1;

  return x;
}

struct Node *RotateLeft(struct Node *x) 
{
  struct Node *y = x->right;
  struct Node *TEMP2 = y->left;

  y->left = x;
  x->right = TEMP2;

  x->height = max(height(x->left), height(x->right)) + 1;
  y->height = max(height(y->left), height(y->right)) + 1;

  return y;
}

int getBalance(struct Node *N) 
{
  if (N == NULL)
    return 0;
  return height(N->left) - height(N->right);
}

struct Node *insertNode(struct Node *node, int Val) 
{
    
  if (node == NULL)
    return (newNode(Val));

  if (Val < node->Val)
    node->left = insertNode(node->left, Val);
  else if (Val > node->Val)
    node->right = insertNode(node->right, Val);
  else
    return node;

  node->height = 1 + max(height(node->left),height(node->right));

  int balance = getBalance(node);
  if (balance > 1 && Val < node->left->Val)
    return RotateRight(node);

  if (balance < -1 && Val > node->right->Val)
    return RotateLeft(node);

  if (balance > 1 && Val > node->left->Val) 
  {
    node->left = RotateLeft(node->left);
    return RotateRight(node);
  }

  if (balance < -1 && Val < node->right->Val) 
  {
    node->right = RotateRight(node->right);
    return RotateLeft(node);
  }

  return node;
}

struct Node *minValueNode(struct Node *node) 
{
  struct Node *current = node;

  while (current->left != NULL)
    current = current->left;

  return current;
}

struct Node *deleteNode(struct Node *root, int Val) 
{
  if (root == NULL)
    return root;

  if (Val < root->Val)
    root->left = deleteNode(root->left, Val);

  else if (Val > root->Val)
    root->right = deleteNode(root->right, Val);

  else 
  {
    if ((root->left == NULL) || (root->right == NULL)) 
    {
      struct Node *temp = root->left ? root->left : root->right;

      if (temp == NULL)
      {
        temp = root;
        root = NULL;
      } 
      else
        *root = *temp;
      free(temp);
    } 
    else 
    {
      struct Node *temp = minValueNode(root->right);

      root->Val = temp->Val;

      root->right = deleteNode(root->right, temp->Val);
    }
  }

  if (root == NULL)
    return root;

  root->height = 1 + max(height(root->left),height(root->right));

  int balance = getBalance(root);
  if (balance > 1 && getBalance(root->left) >= 0)
    return RotateRight(root);

  if (balance > 1 && getBalance(root->left) < 0) 
  {
    root->left = RotateLeft(root->left);
    return RotateRight(root);
  }

  if (balance < -1 && getBalance(root->right) <= 0)
    return RotateLeft(root);

  if (balance < -1 && getBalance(root->right) > 0) 
  {
    root->right = RotateRight(root->right);
    return RotateLeft(root);
  }

  return root;
}

void printPreOrder(struct Node *root) 
{
  if (root != NULL) 
  {
    printf("%d ", root->Val);
    printPreOrder(root->left);
    printPreOrder(root->right);
  }
}

int main() 
{
  struct Node *root = NULL;

  root = insertNode(root, 56);
  root = insertNode(root, 14);
  root = insertNode(root, 86);
  root = insertNode(root, 25);
  root = insertNode(root, 38);
  root = insertNode(root, 69);
  root = insertNode(root, 89);

  printPreOrder(root);

  root = deleteNode(root, 14);

  cout <<"AVL after deletion: " ;
  printPreOrder(root);

  return 0;
}

Implementation of AVL Tree in JAVA

class Node {
  int item, height;
  Node left, right;

  Node(int d) {
    item = d;
    height = 1;
  }
}

class AVL {
  Node root;

  int height(Node N) {
    if (N == null)
      return 0;
    return N.height;
  }

  int max(int a, int b) {
    return (a > b) ? a : b;
  }

  Node RotateRight(Node y) {
    Node x = y.left;
    Node T2 = x.right;
    x.right = y;
    y.left = T2;
    y.height = max(height(y.left), height(y.right)) + 1;
    x.height = max(height(x.left), height(x.right)) + 1;
    return x;
  }

  Node RotateLeft(Node x) {
    Node y = x.right;
    Node T2 = y.left;
    y.left = x;
    x.right = T2;
    x.height = max(height(x.left), height(x.right)) + 1;
    y.height = max(height(y.left), height(y.right)) + 1;
    return y;
  }

  int getBalanceFactor(Node N) {
    if (N == null)
      return 0;
    return height(N.left) - height(N.right);
  }

  Node insertNode(Node node, int item) {

    if (node == null)
      return (new Node(item));
    if (item < node.item)
      node.left = insertNode(node.left, item);
    else if (item > node.item)
      node.right = insertNode(node.right, item);
    else
      return node;

    node.height = 1 + max(height(node.left), height(node.right));
    int balanceFactor = getBalanceFactor(node);
    if (balanceFactor > 1) {
      if (item < node.left.item) {
        return RotateRight(node);
      } else if (item > node.left.item) {
        node.left = RotateLeft(node.left);
        return RotateRight(node);
      }
    }
    if (balanceFactor < -1) {
      if (item > node.right.item) {
        return RotateLeft(node);
      } else if (item < node.right.item) {
        node.right = RotateRight(node.right);
        return RotateLeft(node);
      }
    }
    return node;
  }

  Node nodeWithMimumValue(Node node) {
    Node current = node;
    while (current.left != null)
      current = current.left;
    return current;
  }

  Node deleteNode(Node root, int item) {

    if (root == null)
      return root;
    if (item < root.item)
      root.left = deleteNode(root.left, item);
    else if (item > root.item)
      root.right = deleteNode(root.right, item);
    else {
      if ((root.left == null) || (root.right == null)) {
        Node temp = null;
        if (temp == root.left)
          temp = root.right;
        else
          temp = root.left;
        if (temp == null) {
          temp = root;
          root = null;
        } else
          root = temp;
      } else {
        Node temp = nodeWithMimumValue(root.right);
        root.item = temp.item;
        root.right = deleteNode(root.right, temp.item);
      }
    }
    if (root == null)
      return root;

    root.height = max(height(root.left), height(root.right)) + 1;
    int balanceFactor = getBalanceFactor(root);
    if (balanceFactor > 1) {
      if (getBalanceFactor(root.left) >= 0) {
        return RotateRight(root);
      } else {
        root.left = RotateLeft(root.left);
        return RotateRight(root);
      }
    }
    if (balanceFactor < -1) {
      if (getBalanceFactor(root.right) <= 0) {
        return RotateLeft(root);
      } else {
        root.right = RotateRight(root.right);
        return RotateLeft(root);
      }
    }
    return root;
  }

  void preOrder(Node node) {
    if (node != null) {
      System.out.print(node.item + " ");
      preOrder(node.left);
      preOrder(node.right);
    }
  }

  private void printTree(Node currPtr, boolean last) {
    if (currPtr != null) 
    {
      
      System.out.print(currPtr.item+ " ");
      printTree(currPtr.left, false);
      printTree(currPtr.right, true);
    }
  }

  public static void main(String[] args)
  {
    AVL tree = new AVL();
    tree.root = tree.insertNode(tree.root, 56);
    tree.root = tree.insertNode(tree.root, 14);
    tree.root = tree.insertNode(tree.root, 86);
    tree.root = tree.insertNode(tree.root, 25);
    tree.root = tree.insertNode(tree.root, 38);
    tree.root = tree.insertNode(tree.root, 69);
    tree.root = tree.insertNode(tree.root, 89);
    tree.printTree(tree.root, true);
    tree.root = tree.deleteNode(tree.root, 14);
    System.out.println("AVL After Deletion: ");
    tree.printTree(tree.root, true);
  }
}

Implementation of AVL Tree in Python

import sys
class TreeNode(object):
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1


class AVLTree(object):

    def insert_node(self, root, key):

        if not root:
            return TreeNode(key)
        elif key < root.key:
            root.left = self.insert_node(root.left, key)
        else:
            root.right = self.insert_node(root.right, key)

        root.height = 1 + max(self.getHeight(root.left),self.getHeight(root.right))

        balanceFactor = self.getBalance(root)
        if balanceFactor > 1:
            if key < root.left.key:
                return self.RotateRight(root)
            else:
                root.left = self.RotateLeft(root.left)
                return self.RotateRight(root)

        if balanceFactor < -1:
            if key > root.right.key:
                return self.RotateLeft(root)
            else:
                root.right = self.RotateRight(root.right)
                return self.RotateLeft(root)

        return root

    def delete_node(self, root, key):

        if not root:
            return root
        elif key < root.key:
            root.left = self.delete_node(root.left, key)
        elif key > root.key:
            root.right = self.delete_node(root.right, key)
        else:
            if root.left is None:
                temp = root.right
                root = None
                return temp
            elif root.right is None:
                temp = root.left
                root = None
                return temp
            temp = self.getMinValueNode(root.right)
            root.key = temp.key
            root.right = self.delete_node(root.right,
                                          temp.key)
        if root is None:
            return root

        root.height = 1 + max(self.getHeight(root.left),
                              self.getHeight(root.right))

        balanceFactor = self.getBalance(root)

        if balanceFactor > 1:
            if self.getBalance(root.left) >= 0:
                return self.RotateRight(root)
            else:
                root.left = self.RotateLeft(root.left)
                return self.RotateRight(root)
        if balanceFactor < -1:
            if self.getBalance(root.right) <= 0:
                return self.RotateLeft(root)
            else:
                root.right = self.RotateRight(root.right)
                return self.RotateLeft(root)
        return root

    def RotateLeft(self, z):
        y = z.right
        T2 = y.left
        y.left = z
        z.right = T2
        z.height = 1 + max(self.getHeight(z.left),self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left),self.getHeight(y.right))
        return y

    def RotateRight(self, z):
        y = z.left
        T3 = y.right
        y.right = z
        z.left = T3
        z.height = 1 + max(self.getHeight(z.left),self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left),self.getHeight(y.right))
        return y

    def getHeight(self, root):
        if not root:
            return 0
        return root.height

    def getBalance(self, root):
        if not root:
            return 0
        return self.getHeight(root.left) - self.getHeight(root.right)

    def getMinValueNode(self, root):
        if root is None or root.left is None:
            return root
        return self.getMinValueNode(root.left)

    def preOrder(self, root):
        if not root:
            return
        print("{0} ".format(root.key), end="")
        self.preOrder(root.left)
        self.preOrder(root.right)

    def printAVL(self, currPtr, last):
        if currPtr != None:
            
            print(currPtr.key)
            self.printAVL(currPtr.left, False)
            self.printAVL(currPtr.right, True)


myTree = AVLTree()
root = None
nums = [56, 14, 86, 25, 38, 69, 89]
for num in nums:
    root = myTree.insert_node(root, num)
myTree.printAVL(root, True)
key = 14
root = myTree.delete_node(root, key)
print("After Deletion: ")
myTree.printAVL(root, True)

Complexity of AVL tree

Insertion: O( log n )
Deletion: O( log n )
Search: O( log n )

Applications of AVL Tree

• Searching operations in very large datasets
• Indexing of data in very large databases.

Conclusion

AVL Trees are self-balancing binary trees. If at any point, during insertion or deletion, there is an unbalancing in the tree, it is again balanced by different rotations. AVL Trees are more balanced than red-black trees. AVL Tree is preferred over red-black trees in cases where the insertion and deletion are less frequent.

In further articles, we will learn about another type of binary tree known as spanning tree.