All About AVL Trees

The data structure is a crucial and internal part of every other technology. Unknowingly you are also using different data structures in your life. For example, you turn your cell phone to Google Maps to find an unknown route and insert the destination location. Google Maps uses one of the data structure types for searching the best possible route for you. Different search algorithms are used in the data structure to enhance the search speed in the minimum possible time. And one such searching algorithm is the AVL tree.

AVL tree in data structure was introduced to overcome the searching problem of binary trees and binary search trees. In its worst case, binary search trees are limited to the searching operations, which take more time with increasing tree height. 

Table Of Contents

• What is AVL Tree
• Why We Need an AVL Tree
• Different Rotations of the AVL Tree
• Example of inserting data in an AVL tree

What is AVL tree?

AVL tree is a self-balancing binary tree. It is called self-balancing because it balances itself by undergoing different operations. The balancing factor helps an AVL tree to balance itself.

AVL tree was introduced in 1962 by GM Adelson – Velsky and EM Landis, and the full form of an AVL tree is the Adelson Velsky Landis tree. They invented this search algorithm to overcome the searching problem of a binary search tree.

An AVL tree is a balanced binary search tree that uses a balance factor to balance itself. The balance factor is a parameter to determine the balance of a given node. Its acceptable values are 0, 1, and -1.

Balance factor = height of left subtree – the height of right subtree.

Always check the balance factor from the bottom to the top direction of tree nodes.

• When the value of the balance factor is 1, it means more children on the left side than a child on the right side of the node. 
• When the balance factor is 0, it means an equal number of left and right subtrees of a node.
• When the value of the balance factor is -1, it means more children on the right side compared to the child on the left side of the node

Example to calculate the balance factor

The balance factor other than 1, 0, and -1 result in an unbalanced binary tree. The maximum height of an AVL tree is (logn) and time complexity is also O (logn).

Also Read: Balanced Binary Tree

Also Read: Red Black Tree

Why We Need an AVL Tree

AVL tree was introduced to overcome the limitations of the binary tree and the binary search tree.

1. A binary tree allows data insertion in any order. Random data insertion takes more searching time and results in a less efficient searching algorithm.

2. The binary search tree is efficient when its time complexity is (logn) but the worst case of the binary search tree limits its time efficiency.

In the worst case, the binary search tree grows either in the left direction only or in the right direction only. Resulting in a left-skewed tree or right-skewed tree.

The AVL tree overcomes all the above-mentioned problems. It provides ordered insertion and prevents the tree from being skewed. The term skewed in data structure means an unbalanced tree or a tree with one or no child node.

Different Rotations of the AVL Tree

To balance a node, an AVL tree uses four types of rotations. Before understanding the insertion in an AVL tree its rotations are the pre-requirements.

We will cover each type of rotation with an example in four different cases.

Case 1: RR rotation

It arises when the tree grows in the right direction.

For example, we have to insert 8, 9, and 10 in the tree.

Here node 8 is unbalanced so the tree will rotate in an anticlockwise direction with taking node 9 in the middle. It will be like this.

Now, the tree is balanced with an expectable balance factor.

Also Read: Complete Binary Tree

Case 2: LL Rotation:

This rotation is used when there is more child in the left subtree. To overcome this unbalanced tree, the tree is rotated in a clockwise direction. For example:

Insert 10, 9, and 8. We inserted the data with 10 as the main node and 9 is smaller than 10 so it will be inserted on the left side and 8 is smaller than 10 and 9 so it will be inserted to the left of 9. Calculating the balance factor of each node.

The tree is unbalanced at node 10, to make it a balanced tree. We will rotate it in a clockwise direction from node 9 and the resulting tree is like below:

Now, the tree is balanced.

Case 3: RL Rotation:

In this rotation, the tree grows first in the right direction and then in the left direction. It takes two rotations to balance it.

100 For example, we have to insert 10, 12, and 11 in the tree. Insert the data with the rules of the binary searching tree and calculated the balance factor.

The above tree is unbalanced at node 10 and to make it a balanced tree, it requires two rotations. First, take all nodes to the right side and interchange the position of node 12 and node 11. Like this.

Again, rotate the tree in an anticlockwise direction with LL rotation from node 11 to balance the tree.

Also Read: Spanning Trees

Case 4: LR Rotation

In this rotation, the tree grows in the left direction and then in the right direction. It takes two rotations to balance the tree.

For example, we have to insert 10, 8, and 9. The tree is as follows after inserting the data.

We can see that node 10 is unbalanced to make it a balanced node, interchange the position of nodes 8 and 9 by keeping every node to the left side.

This is the LL case and now rotates node 10 in a clockwise direction by keeping node 9 in middle. Calculate the balance factor of each node.

The above AVL tree is fully balanced.

Also Read: B Tree in Data Structure

Example to insert data in an AVL tree

In this section, we will learn to create an AVL tree while inserting data and simultaneously balancing the tree with different rotations.

Data = 35, 50, 40, 25, 30

Insertion method

The data in an AVL tree are inserted in the same order as a binary search tree. The key principle while insertion is all data are compared with the root node.

• Insert smaller values to the left of the root node.
• Insert larger values to the right of the root node.

35 Here, 35 is the root node as it is the first data.

Inserting 50 and 40 by comparing their values with the root node 35. Calculating the balance factor of each node.

Node 35 is unbalanced and it is a case of RL rotation. To solve this, interchange the position of nodes 50 and 40 while keeping both nodes in the right direction. This results in an RR rotation case. Again, rotate the tree in an anticlockwise direction.

Also Read: Tree Traversal in Data Structure

Inserting data 25 and 30. On inserting data 25, the tree is balanced. When 35 is inserted and calculated the balance factor.

Node 35 is unbalanced and it is a case of LR rotation. To solve it, use the concept of LR rotation, where we interchange the position of nodes 25 and 30 while keeping both of them on the left side. Finally rotate the tree in the clockwise direction to resolve the LL rotation case. Calculate the balance factor.

This is our final AVL tree with nodes that have an expectable balance factor. In this way, keep adding new data and check the balance factor from the bottom to the top direction. Wherever you find unacceptable balance factor values (other than 1, 0, -1), balance the nodes with required rotations.

Conclusion

We reached the end of this article on the AVL tree. In this article, we understand the different AVL tree rotations needed to balance the nodes. AVL tree is used in various database applications. During the deletion of a node from an AVL tree, check the balance factor after node removal, and if it is unbalanced use the required rotations.

Contributed By: Sonal Meenu Singh