All About AVL Trees

All About AVL Trees

8 mins read320 Views Comment
Updated on Feb 17, 2023 11:20 IST

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.

2023_02_MicrosoftTeams-image-176.jpg

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?

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

2023_02_image-79.jpg

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.
  1. 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.

2023_02_image-80.jpg

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.

2023_02_image-81.jpg

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.

2023_02_image-82.jpg

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:

2023_02_image-83.jpg

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.

2023_02_image-84.jpg

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.

2023_02_image-85.jpg

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

2023_02_image-86.jpg

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.

2023_02_image-87.jpg

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.

2023_02_image-88.jpg

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.

2023_02_image-89.jpg

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.

2023_02_image-91.jpg

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

2023_02_image-93.jpg

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.

2023_02_image-94.jpg

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.

2023_02_image-95.jpg

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.

2023_02_image-96.jpg

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

FAQs

What is the AVL tree explain?

AVL tree is a self-balanced binary tree. It uses the balance factor to balance itself on every node insertion and deletion. The balance factor is the difference between the height of the left subtree to the height of the right subtree.

What does AVL stand for in the AVL tree?

AVL tree got its name from its inventors GM Adelson - Velsky and EM Landis. The full form of AVL is Adelson Velsky Landis tree.

What is the AVL tree application?

AVL tree is used in database applications to respond to queries quickly. It is also used in sorting lists and directories.

What is the difference between AVL and BST?

The difference between the AVL and BST is the self-balancing feature of the AVL tree. An AVL tree balances itself with different rotations by calculating the balance factor. BST cannot balance itself.

What is the advantage of AVL?

The advantage of an AVL tree is its self-balancing feature which makes it unique from other trees.

Why AVL is better than BST?

AVL tree is better than BST as AVL tree prevents a tree from being skewed. In the BST, its worst-case results in either a left-skewed or right-skewed tree.

Is the AVL tree a full binary tree?

Yes, the AVL tree is a full binary tree. But, a fully binary tree is not an AVL tree.

What is AVL time complexity?

The time complexity of an AVL tree is O(logn).

About the Author

This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio