What is an AVL Tree in Data Structures

In a binary search tree, optimization is dependent on the order of an inserted element. Most of the BST operations consume O(h) time, where h is the height of the BST. The cost of such operations may become O(n) for a skewed binary tree, where n  is the number of nodes in that tree. Optimization of such operations may be achieved if the minimum height of a tree is maintained. In a binary search tree, it is difficult to maintain almost the same heights of the left and the right subtree. But in the AVL tree, it is possible to maintain a tree where the height of the left subtree and the right subtree is with a maximum difference of one.

What is an AVL Tree in Data Structures

The binary search tree is said to be an AVL tree, if the difference between the heights of the left subtree and the right subtree of every node in the tree is less than or equal to 1 i.e., either -1,0 or 1. In other words, a binary tree is said to be balanced if, for every node, the height of its children differs at most once. In an AVL tree, each node has extra information known as the balance factor. In an AVL tree, the balance factor of each and every node if <= |1|.

Balance factor of a node = Height of a left subtree of a node – Height of a right subtree of a node.

A node is said to be left heavy if the height of its left subtree is one more than the right subtree. Similarly, a node is called right heavy if the height of its left subtree is one less than its right subtree.

The balance factor will be 1 for the left high, -1 for the right high, and 0 for equal heights of the left subtree and the right subtree.

Search Operation in AVL Tree –

The search operation in AVL Tree is similar to the binary tree search operation. The following steps are performed to search for an item in the AVL tree –

• Compare the item to be searched with the root node in the tree.
• If an item is matched with the node, then the item is found. Then terminate the function.
• If the item does not match, then check whether the item is smaller or larger than that node value.
• If the item is smaller, then continue the search process in the left subtree.
• If the item is larger, then continue the search process in the right subtree.
• Repeat the same until the item is found or all the nodes are compared with the item to be searched.

Insertion Operation in AVL Tree

In an AVL tree, a new node is always inserted as a leaf node. The insertion operation is performed as follows –

• Insert the new item into the tree similar to the binary search tree insertion operation.
• After insertion of the item, check the balance factor of every node.
• If the balance factor of every node is 0 or 1 or -1 then the tree is balanced, therefore, go for the next operation.
• If the Balance factor of any node is other than 0 or 1 or -1 then the tree is said to be unbalanced, Then perform one of the following rotations to make a balanced

1. Left to left rotation
2. Right to Right rotation
3. Left to right Rotation
4. Right-to-left rotation

So, in this tutorial, we learned about AVL trees and their operations on them. Although this is not much used, still it is better to know about them.

Attempt Free Data Structures MCQ Test