Last Updated on January 24, 2023 by Sumit Kumar
In this article, we will learn what is AVL tree in data structure, what are different rotations in the AVL tree, the operations of the AVL tree in data structure, and the program to perform various operations on the AVL tree in data structure.
What is the AVL tree in data structure?
The name AVL comes from the inventor of this algorithm GM Adelson, Velsky, and EM Landis. The AVL tree is also called a Height Balanced Binary Search Tree. It is called a height-balanced binary search because the balance factor of each node in the AVL tree is 1,0, or -1. The balance factor of any node is the subtraction of the height of the left sub-tree and the height of the right sub-tree. Let’s see how to calculate the balance factor with an example.
Balance factor of node = height of left sub-tree of – height of right subtree
In the above example, we can see that the height of the left sub-tree is 2, and the height of the right sub-tree is also 2. So, our balance factor for the root node will be 2-2 = 0.
In the above example, we can see that the height of the left sub-tree is 2, and the height of the right sub-tree is also 1. So, our balance factor for the root node will be 2 – 1 = 1.
In the above example, we can see that the height of the left sub-tree is 1, and the height of the right sub-tree is also 2. So, our balance factor for the root node will be 1 – 2 = -1.
Now, we know what is balance factor of the node in the AVL tree is. Let’s see an example of an AVL tree in data structure with a balance factor for each node.
In the above example, we can say the above binary search tree is the AVL tree because the balance factor of each node is either 1 or 0, or -1. Every AVL tree is always a binary search tree but every binary search tree is not always an AVL tree.
Rotations in AVL tree:
There are four types of rotation in the AVL tree:
1. LL Rotation: this rotation is performed when a newly inserted node is in the left sub-tree of the left subtree of the particular node.
2. RR Rotation: this rotation is performed when a newly inserted node is in the right sub-tree of the right subtree of the particular node.
3. LR Rotation: this rotation is performed when a newly inserted node is in the right sub-tree of the left subtree of the particular node.
4. RL Rotation: this rotation is performed when a newly inserted node is in the left sub-tree of the right subtree of the particular node.
LL Rotation:
LL Rotation is performed when a newly added node violates the property of the AVL tree which means it changes the balance factor of a node out of range -1 to 1. Let’s see an example to perform LL Rotation in the AVL tree.
In the above example, we have inserted a new node 10 to the left of left to node 30. We can see that after inserting a new node the balance factor of node 30 becomes 2 and the tree becomes unbalanced. To make this tree balanced tree we will apply LL Rotation on the tree. We will apply the right rotation and after that, we can see the resultant tree becomes balanced.
RR Rotation:
RR Rotation is performed when a newly added node violates the property of the AVL tree which means it changes the balance factor of a node out of range -1 to 1. Let’s see an example to perform RR Rotation in the AVL tree.
In the above example, we have inserted a new node 30 to the right of right to node 10. We can see that after inserting a new node the balance factor of node 10 becomes -2 and the tree becomes unbalanced. To make this tree balanced tree we will apply RR Rotation on the tree. We will apply the left rotation and after that, we can see the resultant tree becomes balanced.
LR Rotation:
LR Rotation is performed when a newly added node violates the property of the AVL tree which means it changes the balance factor of a node out of range -1 to 1. Let’s see an example to perform LR Rotation in the AVL tree.
In the above example, we have inserted a new node 20 to the right of the left to node 30. We can see that after inserting a new node the balance factor of node 30 becomes -2 and the tree becomes unbalanced. To make this tree balanced tree we will apply LR Rotation on the tree. We will apply the left rotation and after that, we will apply the right rotation. Now the tree becomes unbalanced like in the first case and we have to apply LL Rotation. We can see the resultant tree becomes balanced.
RL Rotation:
RL Rotation is performed when a newly added node violates the property of the AVL tree which means it changes the balance factor of a node out of range -1 to 1. Let’s see an example to perform RL Rotation in the AVL tree.
In the above example, we have inserted a new node 20 to the left of the right to node 30. We can see that after inserting a new node the balance factor of node 30 becomes -2 and the tree becomes unbalanced. To make this tree balanced tree we will apply RL Rotation on the tree. We will apply the right rotation and after that, we will apply the left rotation. Now the tree becomes unbalanced like in the second case and we have to apply RR Rotation. We can see the resultant tree becomes balanced.
AVL tree in data structure example with dry-run
Let’s take an example to understand the AVL tree in data structures.
Insertion:
Let’s see how an insertion operation is performed in the AVL tree.
Elements = 17 18 19 11 10
We will try to add each element one by one
insert 17:
We can see that we have inserted 17 in the tree and it becomes the root of the tree. The tree is also balanced.
insert 18:
After inserting 18, we can see that still, the tree is balanced thus we don’t need to modify it.
insert 19:
After inserting 19, we can see that the balance factor of 17 becomes -2 and the tree becomes unbalanced. Now, we will apply RR rotation to the tree and we can see that it becomes a balanced tree after applying RR rotation.
insert 11:
After inserting 11, we can see that the tree is still a balanced tree. So, we do not need to modify it.
insert 10:
After inserting 10, we can see that the balance factor of 17 and 18 becomes 2 and the tree becomes unbalanced. Now, we will apply LL rotation after that, the tree becomes balanced.
Deletion:
Let’s see how a deletion operation is performed in the AVL tree.
We have taken the above example to the AVL tree. Now, let’s try to delete a node from the tree.
In the above image, we can see that we are trying to delete node 19 from the tree.
We can see that after the deletion of node 19, the balance factor of node 18 becomes 2 and the tree becomes unbalanced. Now, we will apply LL rotation to make the tree balanced.
Program of the AVL tree in data structure:
Let’s see how to write a program of the AVL tree in data structure.
class Node {
int data, height;
Node left_child, right_child;
Node(int val){
data = val;
height = 0;
}
}
class AVL_tree{
Node node;
int get_height(Node root){
if(root == null)
return -1;
return root.height;
}
int get_balance_factor(Node root){
if(root == null)
return 0;
return (get_height(root.left_child) - get_height(root.right_child));
}
Node LL_rotation(Node root){
Node child = root.left_child;
root.left_child = child.right_child;
child.right_child = root;
root.height = Math.max(get_height(root.left_child), get_height(root.right_child)) + 1;
child.height = Math.max(get_height(child.left_child), get_height(child.right_child)) + 1;
return child;
}
Node RR_rotation(Node root){
Node child = root.right_child;
root.right_child = child.left_child;
child.left_child = root;
root.height = Math.max(get_height(root.left_child), get_height(root.right_child)) + 1;
child.height = Math.max(get_height(child.left_child), get_height(child.right_child)) + 1;
return child;
}
void pre_order(Node root) {
if (root != null) {
System.out.print(root.data + " ");
pre_order(root.left_child);
pre_order(root.right_child);
}
}
Node insert(Node root, int val){
if (root == null)
return (new Node(val));
if (val < root.data)
root.left_child = insert(root.left_child, val);
else if (val > root.data)
root.right_child = insert(root.right_child, val);
else
return node;
root.height = Math.max(get_height(root.left_child), get_height(root.right_child)) + 1;
int b = get_balance_factor(root);
if(b > 1){
// LL Rotation Case
if(get_balance_factor(root.left_child) == 1){
root = LL_rotation(root);
}
// LR Rotation Case
else{
root.left_child = RR_rotation(root.left_child);
root = LL_rotation(root);
}
}
else if(b < -1){
// RR Rotation Case
if(get_balance_factor(root.right_child) == -1){
root = RR_rotation(root);
}
// RL Rotation Case
else{
root.right_child = LL_rotation(root.right_child);
root = RR_rotation(root);
}
}
return root;
}
public static void main(String[] args) {
AVL_tree tree = new AVL_tree();
tree.node = tree.insert(tree.node, 17);
tree.node = tree.insert(tree.node, 18);
tree.node = tree.insert(tree.node, 19);
tree.node = tree.insert(tree.node, 11);
tree.node = tree.insert(tree.node, 10);
System.out.println("Pre-order Traversal of the AVL Tree is : ");
tree.pre_order(tree.node);
}
}
Output:
Pre-order Traversal of the AVL Tree is:
18 11 10 17 19 Time complexity of the AVL tree:
- Traversal: O(n) where n is the number of totals node of the tree
- Insertion: O(logn) because the max height of the AVL tree will be logn
- Deletion: O(logn)
- Searching: O(logn)
FAQs of the AVL tree in data structure:
1. What is the difference between the binary search tree (BST) and the AVL tree?
The main difference between the binary search tree (BST) and the AVL tree is that the height of the AVL tree is always less than or equal to log(n) while the height of the BST can be n in the worst case (skewed tree).
2. Why the height of the AVL tree is always less than or equal to log(n)?
We know the other name of the AVL tree is the self-balanced binary search tree. This means the binary tree will balance the height by itself. Thus, the height of the AVL tree will be always less than or equal to log(n).
3. What is the balance factor in the AVL tree?
The balance factor is used to find the difference in height between the left subtree and the right subtree. It is also used to check whether the tree is balanced or unbalanced. The balance factor of each node of the AVL tree will be either 1 or 0 or -1.