AVL Tree Data Structure

AVL tree is a height-balanced binary search tree. A binary tree is said to be balanced if, the difference between the heights of left and right subtrees of every node in the tree is either -1, 0 or +1. In an AVL tree, every node maintains an extra information known as balance factor.

The AVL tree was introduced in the year 1962 by G.M. Adelson-Velsky and E.M. Landis.

An AVL tree is a balanced binary search tree. In an AVL tree, balance factor of every node is either -1, 0 or +1.

Balance factor of a node is the difference between the heights of the left and right subtrees of that node. The balance factor of a node is calculated either height of left subtree - height of right subtree (OR) height of right subtree - height of left subtree.

AVL Trees Rotations

In AVL trees, after performing an insertion or deletion operation, if the tree is not balanced, rotations are used to maintain the balance of the tree. There are four types of rotations: left rotation, right rotation, left-right rotation, and right-left rotation.

In AVL Trees, Left and Right rotations required single rotation whereas Left-Right and Right-Left rotation required double rotations.

Left Rotation (LL Rotation)

In the Left Rotation, every node moves one position to left from the current position of the tree. Let us consider the following insertion operation in AVL Tree.

Right Rotation (RR Rotation)

In RR Rotation, every node moves one position to right from the current position. To understand RR Rotation, let us consider the following insertion operation in AVL Tree...

Left Right Rotation (LR Rotation)

The LR Rotation is a sequence of single left rotation followed by a single right rotation. In LR Rotation, at first, every node moves one position to the left and one position to right from the current position. To understand LR Rotation, let us consider the following insertion operation in AVL Tree...

Right Left Rotation (RL Rotation)

The RL Rotation is sequence of single right rotation followed by single left rotation. In RL Rotation, at first every node moves one position to right and one position to left from the current position. To understand RL Rotation, let us consider the following insertion operation in AVL Tree...

Operations on an AVL Trees

Search Operation in AVL Tree

In an AVL tree, the search operation is performed with O(log n) time complexity. The search operation in the AVL tree is similar to the search operation in a Binary search tree. We use the following steps to search an element in AVL tree...

Insertion Operation in AVL Tree

In an AVL tree, the insertion operation is performed with O(log n) time complexity. In AVL Tree, a new node is always inserted as a leaf node. The insertion operation is performed as follows...

Deletion Operation in AVL Tree

The deletion operation in AVL Tree is similar to deletion operation in BST. But after every deletion operation, we need to check with the Balance Factor condition. If the tree is balanced after deletion go for next operation otherwise perform suitable rotation to make the tree Balanced.

Implementation of AVL Tree in Java

  
  // Create a Node class
  class Node {
    int item, height;
    Node left, right;
    
    Node(int data) {
      item = data;
      height = 1;
    }
  }
  
  // AVL tree implementation in Java
  class AVLTree {
    Node root;
    
    int height(Node node) {
      return (node == null) ? 0 : node.height;
    }
    
    int max(int a, int b) {
      return (a > b) ? a : b;
    }
    
    Node rightRotate(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 leftRotate(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;
    }
    
    // Get balance factor of a node
    int getBalanceFactor(Node node) {
      return (node == null ? 0 : (height(node.left) - height(node.right)));
    }
    
    // Method to insert a node a AVL tree 
    Node insertNode(Node node, int item) {
      
      // Find the position and insert the node
      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;
      
      // Update the balance factor of each node and balance the AVL tree
      node.height = 1 + max(height(node.left), height(node.right));
      int balanceFactor = getBalanceFactor(node);
      if (balanceFactor > 1) {
        if (item < node.left.item) {
          return rightRotate(node);
        } else if (item > node.left.item) {
          node.left = leftRotate(node.left);
          return rightRotate(node);
        }
      }
      if (balanceFactor < -1) {
        if (item > node.right.item) {
          return leftRotate(node);
        } else if (item < node.right.item) {
          node.right = rightRotate(node.right);
          return leftRotate(node);
        }
      }
      return node;
    }
    
    Node nodeWithMimumValue(Node node) {
      Node current = node;
      while (current.left != null)
        current = current.left;
      return current;
    }
    
    // Method to delete a node a AVL tree
    Node deleteNode(Node root, int item) {
      // Find the node to be deleted and remove it
      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;
      
      // To balance the AVL tree, update the balance factor of each node
      root.height = max(height(root.left), height(root.right)) + 1;
      int balanceFactor = getBalanceFactor(root);
      
      if (balanceFactor > 1) {
        if (getBalanceFactor(root.left) >= 0) {
          return rightRotate(root);
        } else {
          root.left = leftRotate(root.left);
          return rightRotate(root);
        }
      }
      
      if (balanceFactor < -1) {
        if (getBalanceFactor(root.right) <= 0) {
          return leftRotate(root);
        } else {
          root.right = rightRotate(root.right);
          return leftRotate(root);
        }
      }
      return root;
    }
    
    static void preOrder(Node node) {
      if (node != null) {
        System.out.print(node.item + " ");
        preOrder(node.left);
        preOrder(node.right);
      }
    }
    
    // Method to print elements of an AVL Tree
    static void printAVLTree(Node currPtr, String indent, boolean last) {
      if (currPtr != null) {
        System.out.print(indent);
        if (last) {
          System.out.print("R----");
          indent += "   ";
        } else {
          System.out.print("L----");
          indent += "|  ";
        }
        System.out.println(currPtr.item);
        printAVLTree(currPtr.left, indent, false);
        printAVLTree(currPtr.right, indent, true);
      }
    }
    
    public static void main(String[] args) {
      // Create an AVL Tree
      AVLTree tree = new AVLTree();
      
      // Insert nodes in an AVL Tree
      tree.root = tree.insertNode(tree.root, 45);
      tree.root = tree.insertNode(tree.root, 15);
      tree.root = tree.insertNode(tree.root, 78);
      tree.root = tree.insertNode(tree.root, 11);
      tree.root = tree.insertNode(tree.root, 26);
      tree.root = tree.insertNode(tree.root, 30);
      tree.root = tree.insertNode(tree.root, 55);
      tree.root = tree.insertNode(tree.root, 11);
      
      // Print AVL Tree after adding nodes
      System.out.println("AVL Tree:");
      printAVLTree(tree.root, "", true);
      
      // Delete node (26) in AVL Tree
      tree.root = tree.deleteNode(tree.root, 26);
      
      System.out.println("\nAVL Tree, After Deletion of element 26: ");
      printAVLTree(tree.root, "", true);
    }
  }

Scenario	Use alternative Data Structure
Frequent insertions/deletions operations	Red-Black Trees
Faster insertions/deletions operations	Red-Black Trees
Small datasets	Arrays, Linked Lists
Memory constraints	Unbalanced BSTs, Arrays
Lookup-heavy workloads	Hash Tables
Real-time systems	B-Trees, Red-Black Trees
Required simple implementation	Unbalanced BSTs, Arrays
Not required ordered data	Hash tables

Feature	AVL Tree	Red-Black Tree
Balanced	More balanced	Less balanced
Insertion/Deletion	Slower (more rotations required)	Faster (fewer rotations required)
Searching	Efficient search operations	Less efficient
Node color	No colored node	Node will be either red or black color
Balance factor	All the nodes contain a balance factor (-1, 0, 1)	No balance factor for each node
Processing time	Takes more	Takes less

AVL Tree Data Structure

AVL Trees Rotations

Left Rotation (LL Rotation)

Right Rotation (RR Rotation)

Left Right Rotation (LR Rotation)

Right Left Rotation (RL Rotation)

Operations on an AVL Trees

Search Operation in AVL Tree

Insertion Operation in AVL Tree

Deletion Operation in AVL Tree

Implementation of AVL Tree in Java

Applications of AVL Trees

Advantages of AVL Trees

Disadvantages of AVL Trees

When to Use AVL Trees in Applications

When to Avoid AVL Trees in Applications

Alternatives of AVL Trees in Data Structure

Difference between AVL Tree and Red-Black