In computer science, AVL Tree, named after its Soviet inventors Georgy Adelson-Velsky and Evgenii Landis, is a self-balancing binary search tree (BST).

In this post we will be looking about this wonderful AVL tree.


Note : In all the pseudo codes, 0-based indexing is used and the indentations are used to differentiate between block of codes.


Recap

Binary Search Tree (BST) is binary tree data structure which exhibits the following properties :

  • The left-subtree contains elements that are smaller than the node.
  • The right-subtree contains elements that are greater than the node.
  • The left-subtree and right-subtree are binary search tree themselves.

The main issue with BST is that the time complexity for each operation is O(height) which in the worst case can reach O(N).


AVL Tree was invented in 1962 to reduce the time complexity associated with each operations in Binary Search Tree (BST).

First of its kind to be invented, AVL Tree exhibits certain properties to make sure that the tree is always balanced.

Properties

  • Each tree has a root node (at the top).
  • Each node has a maximum of two and a minimum of zero nodes.
  • For each node, the value at the left-child is less than the value of the node and the value at the right-child is greater than the value of the node.
  • For each node, the difference between the height of the left-child and the right-child can not be more than one.

Structure

As AVL Tree is a kind of BST, each node in AVL Tree consists of two pointers, one to the left child and the other to the right child. In addition to the pointers, each node also consists of two other fields, key and height, which stores the value of the node and the height of the node respectively.

AVLNode{
    int key, height
    AVLNode *left, *right
}

For example, AVL Tree consisting of elements 12, 19, 25, 27, 31, 35, 54, 61,

AVL Tree Example
AVL Tree Example

Create Node

This function returns a pointer to a newly created node with key as specified and height equal to 1.

Pseudo Code :

createNewNode(key)
    AVLNode *toBeReturned=new AVLNode()
    toBeReturned->left=NULL
    toBeReturned->right=NULL
    toBeReturned->key=key
    toBeReturned->height=1
    return toBeReturned

Time Complexity : O(1)


Balance Factor

The balance factor of an AVL Tree is defined as the difference between the height of the left-child and the height of the right-child i.e.

Balance Factor(node)=(node->left)->height-(node->right)->height

To keep the tree balanced, we use two kinds of rotations in AVL Tree namely right-rotation and left-rotation.

Right-Rotation

This rotation takes place when the node is left unbalanced i.e. the height of the left child is greater than height of the right child by at least 2 and hence the balance factor > 1.

Right-Rotation Example
Right-Rotation Example

Pseudo Code :

rightRotate(oldParent)
    AVLNode *newParent=oldParent->left
    oldParent->left=newParent->right
    newParent->right=oldParent
    
    // Updating Heights of oldParent and newParent
    oldParent->height=max(getHeight(oldParent->left),getHeight(oldParent->right))+1
    newParent->height=max(getHeight(newParent->left),getHeight(newParent->right))+1
    
    return newParent

Time Complexity : O(1)

Left-Rotation

This rotation takes place when the node is right unbalanced i.e. the height of the right-child is greater than height of the left-child by at least 2 and hence the balance factor < -1.

Left-Rotation Example
Left-Rotation Example

Pseudo Code :

leftRotate(oldParent)
    AVLNode *newParent=oldParent->right
    oldParent->right=newParent->left
    newParent->left=oldParent
    
    // Updating Heights of oldParent and newParent
    oldParent->height=max(getHeight(oldParent->left),getHeight(oldParent->right))+1
    newParent->height=max(getHeight(newParent->left),getHeight(newParent->right))+1
    
    return newParent

Time Complexity : O(1)


We will use two helper functions to perform basic operations on the AVL Tree namely,

  • getHeight : This function returns the height of the node, returning zero if the node does not exists.
getHeight(node)
    if node==NULL
        return 0
    return node->height
  • getBalanceFactor : This function returns the balance factor of the node, returning zero if the node does not exists.
getBalanceFactor(node)
    if node==NULL
        return 0
    return getHeight(node->left)-getHeight(node->right)

The main beauty of AVL Tree is that it ensures that the tree always remain balanced. The main issue with an unbalanced tree is that each operation in an unbalanced tree is O(height) which in the worst case can be O(N).

A balanced tree can become unbalanced in four ways :

Left-Left Case

Left-Left Case
Left-Left Case

Right-Right Case

Right-Right Case
Right-Right Case

Left-Right Case

Left-Right Case
Left-Right Case

Right-Left Case

Right-Left Case
Right-Left Case

Note : N is the number of the nodes in the AVL Tree.


Insert

We will use three simple steps to insert an element in the AVL tree

  • Finding the Position : We will make use of the BST property to do this job and iterate towards the left-subtree only if the key is less the value of the node and to the right-subtree only if the key is greater than the value of the node. If the key already exists in the AVL tree, we don't insert the node.
  • Adding the Node : A single call to the function createNewNode will do the job for us as soon as we get the desired position.
  • Updating the Tree : We update the height of each node traversed and balance the tree if it has become unbalanced.

Pseudo Code :

insert(node, key)
    if node==NULL
        return createNewNode(key)
    if key<node->key
        node->left=insert(node->left)
    else if key>node->key
        node->right=insert(node->right)
    else
        return node
    
    // Updating Height of node
    node->height=max(getHeight(node->left),getHeight(node->right))+1
    
    // Balancing the AVL Tree after insertion
    balanceFactor=getBalanceFactor(node)
    
    //Left-Left Case
    if balanceFactor>1 and key<node->left->key
        return rightRotate(node)
    //Right-Right Case
    if balanceFactor<-1 and key>node->right->key
        return leftRotate(node)
    //Left-Right Case
    if balanceFactor>1 and key>node->left->key
        node->left=leftRotate(node->left)
        return rightRotate(node)
    //Right-Left Case
    if balanceFactor<-1 and key<node->left->key
        node->right=rightRotate(node->right)
        return leftRotate(node)
        
    return node

Time Complexity : O(logN)

Inserting Elements in AVL Tree
Inserting Elements in AVL Tree

We use the BST property to search for an element in the AVL Tree. At each node there arises three situation,

  • The key to be searched is less than the key of the node. In this case, we search for the key in the left-subtree of the node.
  • The key to be searched is equal to the key of the node. In this case, this is the node we are searching for and hence we return this node.
  • The key to be searched is greater than the key of the node. In this case, we search for the key in the right-subtree of the node.

If any of the above conditions is not met, then the key is not present in the tree, hence we return the NULL pointer.

Pseudo Code :

search(node, key)
    if key==node->key
        return key
    if key<node->key
        return search(node->left, key)
    if key>node->key
        return search(node->right, key)
    return NULL

Time Complexity : O(logN)

Searching 28 in AVL Tree
Searching 28 in AVL Tree

Delete

We make use of another helper function minValue, returning the minimum value in the subtree of the node, to perform the deletion operation.

We use the same set of steps just like in the insert operation in delete operation :

  • Find the Position : Just like what we do during insertion, we use the BST operation to find the position. If the node is not present then we return a NULL pointer.
  • Delete the Node :

Two kinds of situation arises on deleting a node :

  1. The node to be deleted has only one child. In which case, we replace the node with its child.
  2. The node to be deleted has both the children. In this case, we replace the node with the smallest node in the right-subtree.
  • Update the Tree : We update the height of each node traversed in the AVL tree. We also balance the tree if it has become unbalanced.

Pseudo Code :

minValue(node)
    AVLNode *current=node
    while current->left!=NULL
        current=current->left
    return current

delete(node, key)
    if node==NULL
        return node
    if key<node->key
        node->left=delete(node->left, key)
    else if key>node->key
        node->right=delete(node->right, key)
    else
        if node->left==NULL or node->right==NULL
            AVLNode *tempNode=node->left?node->left:node->right
            if tempNode==NULL
                tempNode=node
                node=NULL
            else
                node=tempNode
            free tempNode
        else
            // Get Smallest Node in the Right Subtree
            AVLNode *tempNode=minValue(node->right)
            node->key=tempNode->key
            node->right=delete(node->right, tempNode->key)
    
    // Updating Height of node
    node->height=max(getHeight(node->left),getHeight(node->right))+1
    
    // Balancing the AVL Tree after deletion
    balanceFactor=getBalanceFactor(node)
    
    // Left-Left Case
    if balanceFactor>1 and getBalanceFactor(node->left)>=0
    	return rightRotate(node)
    // Right-Right Case    
    if balanceFactor<-1 and getBalanceFactor(node->right)<=0
    	return leftRotate(node)
    // Left-Right Case
    if balanceFactor>1 and getBalanceFactor(node->left)<0
        node->left=leftRotate(node->left)
        return rightRotate(node)
    // Right-Left Case
    if balanceFactor<-1 and getBalanceFactor(node->right)>0
        node->right=rightRotate(node->right)
        return leftRotate(node)
        
    return node

Time Complexity : O(logN)

Deleting Element from AVL Tree
Deleting Element from AVL Tree

Applications

AVL Trees can be used in databases, for indexing large records and searching. AVL Trees are particularly suited for situations where deletion and insertion are not that frequent but you have to frequently search for items.


Besides AVL Tree, there are other self-balancing trees like Red-Black Tree which offers other benefits however I will leave them for other posts.