The AVL tree in C is a height-balanced binary search tree which means it is also a binary tree that is balanced by the left and right subtree of a node. The tree is said to be balanced when the balance factor of each node is either -1, 0, or +1.
The Balance factor of a tree can be defined as:
Balanced Factor(X) = height(left Subtree (X)) – height(right Subtree(X))
Example of AVL Tree:
The above binary search tree is satisfying the condition of the balance factor, so it is an AVL tree.
There are basically three kinds of operations that are performed in the AVL tree:
To perform these operations, we have to do the following four kinds of rotations:
- LL Rotation (Left Rotation)
- RR Rotation (Right Rotation)
- LR Rotation (Left Right Rotation)
- RL Rotation (Right Left Rotation)
Let’s discuss these operations in detail and understand how these rotations work.
In LL rotation, all the nodes are moved by one position to the left. To understand LL rotation, we have to take into consideration the following insertion operation.
Example: Insert 5, 6, and 9
In RR rotation, all the nodes are moved by one position to the right. To understand RR rotation, we have to take into consideration the following insertion operation.
Example: Insert 5, 4, and 3
In LR rotation, at the first step, every node moves to the left and then moves one step to the right from the current position. Let’s understand the LR rotation with the given example.
Example: Insert 6, 4, and 5
In RL rotation, at the first step, every node moves to the right and then moves one step to the left from the current position. Let’s understand the RL rotation with the given example.
Example: Insert 4, 6, and 5
Write a C program to perform the operations of the AVL tree and display its traversals.
An AVL (Adelson-Velskii and Landis) tree is a self-height balance tree. These trees are binary search trees in which the height of two siblings are not allowed to differ by more than one. We have used the doubly linked list implementation of the AVL tree in which every node contains the address of the left and right children and the data.
Here, we are implementing the main operations of the AVL tree these are given below:
- Insert
- Delete
- Search
Here is source code of the C Program to Implement AVL Tree. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
/*
* AVL Tree Program in C
*/
#include<stdio.h>
#include<stdlib.h>
// structure of the tree node
struct node
{
int data;
struct node* left;
struct node* right;
int ht;
};
// global initialization of root node
struct node* root = NULL;
// function prototyping
struct node* create(int);
struct node* insert(struct node*, int);
struct node* delete(struct node*, int);
struct node* search(struct node*, int);
struct node* rotate_left(struct node*);
struct node* rotate_right(struct node*);
int balance_factor(struct node*);
int height(struct node*);
void inorder(struct node*);
void preorder(struct node*);
void postorder(struct node*);
int main()
{
int user_choice, data;
char user_continue = 'y';
struct node* result = NULL;
while (user_continue == 'y' || user_continue == 'Y')
{
printf("\n\n------- AVL TREE --------\n");
printf("\n1. Insert");
printf("\n2. Delete");
printf("\n3. Search");
printf("\n4. Inorder");
printf("\n5. Preorder");
printf("\n6. Postorder");
printf("\n7. EXIT");
printf("\n\nEnter Your Choice: ");
scanf("%d", &user_choice);
switch(user_choice)
{
case 1:
printf("\nEnter data: ");
scanf("%d", &data);
root = insert(root, data);
break;
case 2:
printf("\nEnter data: ");
scanf("%d", &data);
root = delete(root, data);
break;
case 3:
printf("\nEnter data: ");
scanf("%d", &data);
result = search(root, data);
if (result == NULL)
{
printf("\nNode not found!");
}
else
{
printf("\n Node found");
}
break;
case 4:
inorder(root);
break;
case 5:
preorder(root);
break;
case 6:
postorder(root);
break;
case 7:
printf("\n\tProgram Terminated\n");
return 1;
default:
printf("\n\tInvalid Choice\n");
}
printf("\n\nDo you want to continue? ");
scanf(" %c", &user_continue);
}
return 0;
}
// creates a new tree node
struct node* create(int data)
{
struct node* new_node = (struct node*) malloc (sizeof(struct node));
// if a memory error has occurred
if (new_node == NULL)
{
printf("\nMemory can't be allocated\n");
return NULL;
}
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
// rotates to the left
struct node* rotate_left(struct node* root)
{
struct node* right_child = root->right;
root->right = right_child->left;
right_child->left = root;
// update the heights of the nodes
root->ht = height(root);
right_child->ht = height(right_child);
// return the new node after rotation
return right_child;
}
// rotates to the right
struct node* rotate_right(struct node* root)
{
struct node* left_child = root->left;
root->left = left_child->right;
left_child->right = root;
// update the heights of the nodes
root->ht = height(root);
left_child->ht = height(left_child);
// return the new node after rotation
return left_child;
}
// calculates the balance factor of a node
int balance_factor(struct node* root)
{
int lh, rh;
if (root == NULL)
return 0;
if (root->left == NULL)
lh = 0;
else
lh = 1 + root->left->ht;
if (root->right == NULL)
rh = 0;
else
rh = 1 + root->right->ht;
return lh - rh;
}
// calculate the height of the node
int height(struct node* root)
{
int lh, rh;
if (root == NULL)
{
return 0;
}
if (root->left == NULL)
lh = 0;
else
lh = 1 + root->left->ht;
if (root->right == NULL)
rh = 0;
else
rh = 1 + root->right->ht;
if (lh > rh)
return (lh);
return (rh);
}
// inserts a new node in the AVL tree
struct node* insert(struct node* root, int data)
{
if (root == NULL)
{
struct node* new_node = create(data);
if (new_node == NULL)
{
return NULL;
}
root = new_node;
}
else if (data > root->data)
{
// insert the new node to the right
root->right = insert(root->right, data);
// tree is unbalanced, then rotate it
if (balance_factor(root) == -2)
{
if (data > root->right->data)
{
root = rotate_left(root);
}
else
{
root->right = rotate_right(root->right);
root = rotate_left(root);
}
}
}
else
{
// insert the new node to the left
root->left = insert(root->left, data);
// tree is unbalanced, then rotate it
if (balance_factor(root) == 2)
{
if (data < root->left->data)
{
root = rotate_right(root);
}
else
{
root->left = rotate_left(root->left);
root = rotate_right(root);
}
}
}
// update the heights of the nodes
root->ht = height(root);
return root;
}
// deletes a node from the AVL tree
struct node * delete(struct node *root, int x)
{
struct node * temp = NULL;
if (root == NULL)
{
return NULL;
}
if (x > root->data)
{
root->right = delete(root->right, x);
if (balance_factor(root) == 2)
{
if (balance_factor(root->left) >= 0)
{
root = rotate_right(root);
}
else
{
root->left = rotate_left(root->left);
root = rotate_right(root);
}
}
}
else if (x < root->data)
{
root->left = delete(root->left, x);
if (balance_factor(root) == -2)
{
if (balance_factor(root->right) <= 0)
{
root = rotate_left(root);
}
else
{
root->right = rotate_right(root->right);
root = rotate_left(root);
}
}
}
else
{
if (root->right != NULL)
{
temp = root->right;
while (temp->left != NULL)
temp = temp->left;
root->data = temp->data;
root->right = delete(root->right, temp->data);
if (balance_factor(root) == 2)
{
if (balance_factor(root->left) >= 0)
{
root = rotate_right(root);
}
else
{
root->left = rotate_left(root->left);
root = rotate_right(root);
}
}
}
else
{
return (root->left);
}
}
root->ht = height(root);
return (root);
}
// search a node in the AVL tree
struct node* search(struct node* root, int key)
{
if (root == NULL)
{
return NULL;
}
if(root->data == key)
{
return root;
}
if(key > root->data)
{
search(root->right, key);
}
else
{
search(root->left, key);
}
}
// inorder traversal of the tree
void inorder(struct node* root)
{
if (root == NULL)
{
return;
}
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
// preorder traversal of the tree
void preorder(struct node* root)
{
if (root == NULL)
{
return;
}
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
// postorder traversal of the tree
void postorder(struct node* root)
{
if (root == NULL)
{
return;
}
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
The AVL tree is an extension to the binary search tree in which it is required to balance the height difference between the left and right subtree of a node. We can balance the height of the tree by rotations. Let’s understand the main operations of the AVL Tree with the examples and also discuss their time and space complexities.
On Inserting a new node into the AVL Tree it is necessary to maintain the balance factor of the tree. To insert a new node into the AVL tree, we have to follow the given steps:
- Insert a new element in the tree with the same binary search tree logic.
- Check the balance factor for each node.
- If the balanced factor is not -1 or 0 or +1 of any node then do the proper rotations else terminate.
Example: We are constructing the AVL Tree by inserting the following values.
10 | 15 | 20 | 9 | 5 | 16 | 17 | 8 | 6 |
Step 1: Insert a new node 10
Step 2: Insert a new node 15
Step 3: Insert a new node 20
Step 4: Insert a new node 9
Step 5: Insert a new node 5
Step 6: Insert a new node 16
Step 7: Insert a new node 17
Step 8: Insert a new node 8
Step 9: Insert a new node 6
Time Complexity: O(log n)
Time complexity of an AVL tree is O(log n). Inserting any node in the AVL tree takes logarithmic time because each call skips half the tree to determine the correct position to insert a node.
Space Complexity: O(n)
The space complexity of an avl tree is O(n), because the function calling stack eventually exceeds the number of nodes in the tree.
In this case, we are inserting the nodes into AVL tree and finding traversals.
------- AVL TREE -------- 1. Insert 2. Delete 3. Search 4. Inorder 5. Preorder 6. Postorder 7. EXIT Enter Your Choice: 1 Enter data: 34 Do you want to continue? y ------- AVL TREE -------- 1. Insert 2. Delete 3. Search 4. Inorder 5. Preorder 6. Postorder 7. EXIT Enter Your Choice: 1 Enter data: 78 Do you want to continue? y ------- AVL TREE -------- 1. Insert 2. Delete 3. Search 4. Inorder 5. Preorder 6. Postorder 7. EXIT Enter Your Choice: 1 Enter data: 99 Do you want to continue? y ------- AVL TREE -------- 1. Insert 2. Delete 3. Search 4. Inorder 5. Preorder 6. Postorder 7. EXIT Enter Your Choice: 4 34 78 99 Do you want to continue? y ------- AVL TREE -------- 1. Insert 2. Delete 3. Search 4. Inorder 5. Preorder 6. Postorder 7. EXIT Enter Your Choice: 5 78 34 99 Do you want to continue? y ------- AVL TREE -------- 1. Insert 2. Delete 3. Search 4. Inorder 5. Preorder 6. Postorder 7. EXIT Enter Your Choice: 6 34 99 78 Do you want to continue? n
Deletion of a node is similar to that of deleting a node in the binary search tree. In AVL Tree, after deleting the node we have to maintain the balanced factor again. We need to follow the given steps to delete a node in AVL Tree:
- Search the element in the tree
- Delete the node
- There are two cases that are possible after deletion
- Deleting from the right subtree
- Deleting from the left subtree
Case 1: Deleting a Node from the Right Subtree
There are three subcases that are discussed below:
a) Perform LL rotation when after deletion of a node the balance factor of a node changes to +2 and the balance factor of its left child is +1.
b) Perform LL rotation when after deletion of a node the balance factor of a node changes to +2 and the balance factor of its left child is 0.
c) Perform LR rotation when after deletion of a node the balance factor of a node changes to +2 and the balance factor of its left child is -1.
Case 2: Deleting a Node from the Left Subtree
There are three subcases that are discussed below:
a) Perform RR rotation when after deletion of a node the balance factor of a node changes to -2 and the balance factor of its left child is -1.
b) Perform RR rotation when after deletion of a node the balance factor of a node changes to -2 and the balance factor of its left child is 0.
c) Perform RL rotation when after deletion of a node the balance factor of a node changes to -2 and the balance factor of its left child is 1.
Time Complexity: O(log n)
To delete a node from the AVL tree, it takes logarithmic time to find and delete the given node i.e O(log n).
Space Complexity: O(n)
It takes n function calls for deletion and rebuilding the node from the AVL tree.
In this case, we are deleting the nodes from the AVL tree.
------- AVL TREE -------- 1. Insert 2. Delete 3. Search 4. Inorder 5. Preorder 6. Postorder 7. EXIT Enter Your Choice: 1 Enter data: 34 Enter Your Choice: 1 Enter data: 78 Enter Your Choice: 1 Enter data: 99 Do you want to continue? y ------- AVL TREE -------- 1. Insert 2. Delete 3. Search 4. Inorder 5. Preorder 6. Postorder 7. EXIT Enter Your Choice: 4 34 78 99 Do you want to continue? y ------- AVL TREE -------- 1. Insert 2. Delete 3. Search 4. Inorder 5. Preorder 6. Postorder 7. EXIT Enter Your Choice: 2 Enter data: 78 Do you want to continue? y ------- AVL TREE -------- 1. Insert 2. Delete 3. Search 4. Inorder 5. Preorder 6. Postorder 7. EXIT Enter Your Choice: 4 34 99
Searching a node in an AVL tree is a similar process that we do in a binary search Tree. Follow the given steps to search a node in AVL Tree.
- Start comparing the key with the root node of the tree.
- If the key is greater than the node value then move to the right subtree.
- If the key is less than the node value then move to the left subtree.
- Repeat the process until the key is not found.
Time Complexity: O(log n)
It takes logarithmic time to search any node in the AVL tree.
Space Complexity: O(h)
There are h function calls required to find the node in the AVL tree, where h is the height of the AVL tree.
In this case, we are searching the node in the AVL tree.
------- AVL TREE -------- 1. Insert 2. Delete 3. Search 4. Inorder 5. Preorder 6. Postorder 7. EXIT Enter Your Choice: 1 Enter data: 34 Enter Your Choice: 1 Enter data: 78 Enter Your Choice: 1 Enter data: 99 Do you want to continue? y ------- AVL TREE -------- 1. Insert 2. Delete 3. Search 4. Inorder 5. Preorder 6. Postorder 7. EXIT Enter Your Choice: 4 34 78 99 Do you want to continue? y ------- AVL TREE -------- 1. Insert 2. Delete 3. Search 4. Inorder 5. Preorder 6. Postorder 7. EXIT Enter Your Choice: 3 Enter data: 99 Node found Do you want to continue? y ------- AVL TREE -------- 1. Insert 2. Delete 3. Search 4. Inorder 5. Preorder 6. Postorder 7. EXIT Enter Your Choice: 3 Enter data: 66 Node not found! Do you want to continue? n
To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.
- Apply for Computer Science Internship
- Practice Design & Analysis of Algorithms MCQ
- Practice Programming MCQs
- Check Data Structure Books
- Check Programming Books