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

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,

## 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

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.

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.

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 :

### 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)

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)

## 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)