What is an AVL Tree in Data Structure? | Data Structure Tutorial

In this article, you will understand AVL Tree in brief.

AVL tree is a self-balancing binary tree in which each node keeps the other information of the balance factor whose value is either -1, 0, or +1. The inverters of the AVL tree are Georgy Adelson Velsky and Landis, that’s why they put the name AVL tree. 

Balance Factor

The Balance Factor of a node in an AVL tree is calculated when the height of the left subtree and the height of the right subtree of the node are subtracted. 

Example:

Balance Factor = (Height of Left Subtree - Height of Right Subtree) 

Or 

Balance Factor = (Height of Right Subtree - Height of Left Subtree)

The balance factor of an AVL tree helps in maintaining the self-balancing property. The value of the balance factor is always -1, 0, or +1.

Operations on an AVL tree

Operations that can be performed on an AVL tree are:

Rotate the subtrees in an AVL Tree

In the rotation operation of an AVL tree, the positions of the nodes of the left and right subtree are interchanged. 

The two types of rotations are:

Left Rotate: The position of the nodes on the right is transformed into the position on the left node.

Algorithm:

1. Let’s take the initial tree.
2. If i has a left subtree, assign j as the parent of the left subtree of i.
3. Now, if the parent of the j is NULL, then make i the root of the tree.
4. If j is the left child of z, make i as the left child of z.
5. Otherwise, assign i as the right child of the z.
6. Make i as the parent of j.

Right Rotate: The position of the nodes on the left is transformed into the position on the right node.

Algorithm:

1. Let’s take the initial tree.
2. If j has a right subtree, assign i as the parent of the right subtree of j.
3. Now, if the parent of the i is NULL, then make j the root of the tree.
4. If i is the right child of z, make j as the right child of z.
5. Otherwise, assign j as the left child of the z.
6. Make j as the parent of i.

Left-Right and Right-Left Rotation

In left-right rotation, the positions are initially shifted to the left and then to the right and in right-left rotation, the positions are initially shifted to the right and then to the left.

Algorithm to insert a new Node

A new node is always inserted as a leaf node whose balance factor is always equal to 0.

1. Let’s take the initial tree.
2. Traverse to the leaf node to add a new node with the help of the following steps:
1. Perform the comparison between the newKey with the rootkey of the current tree.
2. If the value of the newkey is less than the value of the rootkey, call the insertion algorithm on the left subtree of the current node until it does not reach the leaf node.
3. If the value of the newkey is greater than the value of the rootkey, call the insertion algorithm on the right subtree of the current node until it does not reach the leaf node.
4. Otherwise, just return the leafNode.
3. Do the comparison of leafkey with newkey:
1. If the value of the newkey is less than the leafkey, make the new node as the left child of the leafnode.
2. Otherwise, make the newNode the right child of the leafNode.
4. Now, update the value of the balance factor of the nodes.
5. Rebalance the node, if the nodes are not balanced:
1. If the balancefactor > 1, that means the height of the left subtree is greater than that of the right subtree. So, do a right rotation or left-right rotation. 
1. If the value of the newNodekey is less than the leftchildkey, do a right rotation.
2. Else, do left-right rotation.
2. If the balancefactor< -1, that means the height of the right subtree is greater than that of the left subtree. So, do a right rotation or right-left rotation.
1. If the value of newNodekey is greater than the value of rightchildkey do a left rotation.
2. Else, perform right-left rotation.
6. Hence, you will obtain the final tree.

Application of AVL Tree

• It is used for indexing large records in databases.
• It can help search the records in large databases.