AVL Tree
AVL Tree
AVL Tree is referred to as self-balanced or height-balanced binary search tree where the difference between heights of its left subtree and right subtree (Balance Factor) can't more than one for all nodes covered by a tree.
Example:
We can say a tree is balanced if the balance factor of each node of a tree is in between -1 to 1; otherwise, a tree is considered as unbalanced and need to balance.
Balance Factor (node) = height (left (node)) – height (right (node))
- If the balance factor is 1 of any node of the tree, then we can say the height of the left subtree is higher than the height of the right subtree of the node in the AVL tree.
- If the balance factor is 0 of any node of the tree, then we can say the height of the left subtree is equal to the height of the right subtree of the node in the AVL tree.
- If the balance factor is -1 of any node of the tree, then we can say the height of the left subtree is lower than the height of the right subtree of the node in the AVL tree.
Need for AVL Trees
If we talk about operations of binary search tree take O (log n) time. The time complexity of these operations could be O(n) if the binary search tree skewed (if the input to the binary search tree comes in an ascending or descending manner) and if we make sure the height of the binary search tree is balanced so we can guarantee that all these operations will take O(log n) time.
AVL Tree Operations
As we discussed, the AVL tree is a special type of binary search tree, so the operations of the AVL tree are the same as the binary search tree without violation of AVL property.
- Insertion: -
In this, we add a new node to the AVL tree. Sometimes it may lead to violating the property of AVL, so we need to re-balance the tree by applying the rotation on it.
- Deletion: -
In this, we delete a node from the AVL tree. It may disturb the balance of the AVL tree, so the tree needs to be re-balanced.
Rotations of AVL Tree:
There are four types of rotations of AVL, which are given below:
- Right Rotation on AVL Tree: -
When the AVL tree is unbalanced because a node is inserted into the left subtree of the Z in the AVL tree, then we have to perform the right rotation on AVL; it is a clockwise rotation.
- Left Rotation on AVL Tree: -
When the AVL tree is unbalanced because a node is inserted into the right subtree of Z in the AVL tree, then we have to perform left rotation on AVL; it is an anti-clockwise rotation.
- Left - Right Rotation on AVL Tree
Doubled rotation is a bit difficult version of AVL rotation. In Left - Right rotation, we perform the left rotation first, then the right rotation after it.
| A node has been added into the right subtree of the left subtree. Because of this, Z becomes an unbalanced node. So, we need to perform left-right rotation on this type of problem in the AVL tree. | |
| Firstly, we need to perform the left rotation on the left subtree of Z. This makes X the left subtree of Y. | |
| Node z is not balanced yet; it is because of the left-sub tree of the left-sub tree in the AVL tree, or its balance factor is still 2. | |
| We have to make Y the new root node of the tree by doing the right rotation on Z. Now, Z becomes the right subtree of Y. | |
| The tree is now balanced. |
- Right - Left Rotation on AVL Tree: -
It is another type of double rotation version. In the right – Left rotation, we perform the right rotation first, then the left rotation after it.
| A node has been added into the left subtree of the right subtree. Because of this, X becomes an unbalanced node with balance factor -2, so we have to balance the AVL tree by performing right-left rotation on it. | |
| First of all, we perform the right rotation on the Z node, making Z the right subtree of the Y subtree. Now, Y becomes the right subtree of X in the AVL tree. | |
| Node X is not balanced yet, because of the right subtree of its right subtree in the AVL tree or its balance factor is still -2. | |
| We have to make Y the new root node of the tree by doing a left rotation on X. Now X becomes the left subtree of Y. | |
| Now, the tree is balanced. |
Implementation of AVL Tree in C Language: -
#include<stdio.h>
typedef struct node
{
int data;
struct node *left, *right;
int ht;
}node;
node *insert(node *, int);
node *Delete(node *, int);
void preorder(node *);
void inorder(node *);
int height( node *);
node *rotate_right(node *);
node *rotate_left(node *);
node *right_rotation(node *);
node *left_rotation(node *);
node *left_right_rotation(node *);
node *right_left_rotation(node *);
int balance_factor(node *);
int main()
{
node *root = NULL;
int x, n, i, op;
do
{
printf("\n1)Create: ");
printf("\n2)Insert: ");
printf("\n3)Delete: ");
printf("\n4)Print: ");
printf("\n5)Quit: ");
printf("\n\nEnter Your Choice: ");
scanf("%d", &op);
switch (op)
{
case 1: printf("\nEnter no. of elements: ");
scanf("%d", &n);
printf("\nEnter tree data: ");
root = NULL;
for(i = 0; i<n; i++)
{
scanf("%d", &x);
root = insert(root, x);
}
break;
case 2: printf("\nEnter a data: ");
scanf("%d", &x);
root = insert(root, x);
break;
case 3: printf("\nEnter a data: ");
scanf("%d", &x);
root = Delete(root, x);
break;
case 4: printf("\nPreorder sequence: \n");
preorder( root );
printf("\n\nInorder sequence: \n");
inorder( root );
printf("\n");
break;
}
}while(op != 5);
return 0;
}
node * insert(node *temp, int x)
{
if(temp == NULL)
{
temp = (node*) malloc (sizeof(node));
temp->data = x;
temp->left = NULL;
temp->right = NULL;
}
else
if(x > temp-> data) // insert in right sub tree
{
temp->right = insert(temp->right, x);
if(balance_factor(temp) == -2)
if(x>temp->right->data)
temp = right_rotation(temp);
else
temp = right_left_rotation(temp);
}
else
if(x < temp->data)
{
temp->left = insert(temp->left, x);
if(balance_factor(temp) == 2)
if(x < temp->left->data)
temp = left_rotation(temp);
else
temp = left_right_rotation(temp);
}
temp->ht = height(temp);
return(temp);
}
node * Delete(node *temp, int x)
{
node *p;
if(temp == NULL)
{
return NULL;
}
else
if(x > temp->data) // insert in right sub tree
{
temp->right = Delete(temp->right, x);
if(balance_factor(temp) == 2)
if(balance_factor(temp->left) >= 0)
temp = left_rotation(temp);
else
temp = left_right_rotation(temp);
}
else
if(x < temp->data)
{
temp->left = Delete(temp->left,x);
if(balance_factor(temp) == -2) //Rebalance tree
if(balance_factor(temp->right)<=0)
temp = right_rotation(temp);
else
temp = right_left_rotation(temp);
}
else
{
// data to be deleted is found
if(temp->right != NULL)
{ //delete its inorder succesor
p = temp->right;
while(p->left != NULL)
p = p->left;
temp->data = p->data;
temp->right = Delete(temp->right, p->data);
if(balance_factor(temp) == 2) //Rebalance tree
if(balance_factor(temp->left) >= 0)
temp = left_rotation(temp);
else
temp = left_right_rotation(temp);
}
else
return(temp->left);
}
temp->ht = height(temp);
return(temp);
}
int height(node * temp)
{
int lh,rh;
if(temp == NULL)
return(0);
if(temp->left == NULL)
lh = 0;
else
lh = 1+ temp->left->ht;
if(temp->right == NULL)
rh = 0;
else
rh = 1+ temp->right->ht;
if(lh > rh)
return(lh);
return(rh);
}
node * rotate_right(node *x)
{
node *y;
y = x->left;
x->left = y->right;
y->right = x;
x->ht = height(x);
y->ht = height(y);
return(y);
}
node * rotate_left(node *x)
{
node *y;
y = x->right;
x->right = y->left;
y->left = x;
x->ht = height(x);
y->ht = height(y);
return(y);
}
node * right_rotation(node *temp)
{
temp = rotate_left(temp);
return(temp);
}
node * left_rotation(node *temp)
{
temp = rotate_right(temp);
return(temp);
}
node * left_right_rotation(node *temp)
{
temp->left = rotate_left(temp->left);
temp = rotate_right(temp);
return(temp);
}
node * right_left_rotation(node *temp)
{
temp->right = rotate_right(temp->right);
temp = rotate_left(temp);
return(temp);
}
int balance_factor(node *temp)
{
int lh,rh;
if(temp == NULL)
return(0);
if(temp->left == NULL)
lh = 0;
else
lh = 1+temp->left->ht;
if(temp->right == NULL)
rh = 0;
else
rh = 1+temp->right->ht;
return(lh - rh);
}
void preorder(node *temp)
{
if(temp != NULL)
{
printf("%d(Bf = %d)", temp->data,balance_factor(temp));
preorder(temp->left);
preorder(temp->right);
}
}
void inorder(node *temp)
{
if(temp != NULL)
{
inorder(temp->left);
printf("%d(Bf = %d)",temp->data, balance_factor(temp));
inorder(temp->right);
}
}
Output: -
Time Complexity of AVL Tree
The rotations of the AVL tree take constant time. It is a self-balanced tree, so the time complexity of all the operations (e.g., insertion, deletion and searching) is O (log n).
Applications of AVL Tree
- It is used for indexing large records in the database.
- Also, it is used for efficient searching or finding the record from the database efficiently.