Updated April 4, 2023
Introduction to AVL tree C program
AVL tree in C program is defined as an algorithm that is written in C programming language, of the AVL tree is a self-balancing Binary Search Tree named after the inventors Adelson, Velski & Landis where the left and the right nodes of the tree are balanced. The intention of a Binary Search Tree is to have an optimized time complexity in terms of search, insert or delete operations. In this article, we will look at how the AVL tree works in general and more specifically look into the working of the same, particularly in the C programming language. We would also look at the practical learning of AVL trees through examples and understand the insert, search and delete operations in the C programming language.
Syntax
Retrieve the value of root in a Binary Search tree:
root->keyPoint to the left of the root in a Binary Search tree:
root->leftPoint to the right of the root in a Binary Search tree:
root->rightHow AVL tree works in the C program?
In an AVL tree, the search operation works similarly to the search operation in BST. In a binary tree, the worst-performing order of time is O(n) in terms of a skewed binary tree. Where the binary tree it is arranged in such a way that the search operation happens like a linear search. Now, if we try to make the height of the tree in the order of O(log n), then the time complexity can be guaranteed to be of the order of O(log n). this is the job of an AVL tree, where it is made sure that the difference between the left-side versus the right-side’s height of the tree is not more than 1.
In order to achieve the same, we perform 2 operations during the insertion known as left rotation and right rotation making sure that the BST property of keys on the left side < root key < keys on the right side. We perform left rotation when we see that the right side’s height is significantly more than the left side and hence the balance of the tree is required. In the process of left rotation, the right child of a node “A”, say “B” becomes the parent node of “A” and the corresponding left child of “B” becomes the right child of “A”. On the other hand, the right rotation is just the vice versa of the left and is done specifically when the left side’s height is significantly more than the right side. Pictorially we can denote the operation to be (In the below diagram the tree on the left side is left rotated):
We can now see that after the tree’s left rotation, we get a balanced tree, and hence the balance is kept after each inserts so that the optimization is achieved. It is now time for us to look at the example to understand the improvisation on a Binary Search Tree to make it an AVL tree.
Examples
Here are the following examples mentioned below.
Example #1
Insert and Delete in AVL Binary Search Tree in C.
Syntax
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int key;
struct Node *lft;
struct Node *rgt;
int height;
};
int max(int a, int b);
int height(struct Node *N)
{
if (N == NULL)
return 0;
return N->height;
}
int max(int a, int b)
{
return (a > b)? a : b;
}
struct Node* newNode(int key)
{
struct Node* node = (struct Node*)
malloc(sizeof(struct Node));
node->key = key;
node->lft = NULL;
node->rgt = NULL;
node->height = 1;
return(node);
}
struct Node *rgtRotate(struct Node *y)
{
struct Node *x = y->lft;
struct Node *T2 = x->rgt;
x->rgt = y;
y->lft = T2;
y->height = max(height(y->lft), height(y->rgt))+1;
x->height = max(height(x->lft), height(x->rgt))+1;
return x;
}
struct Node *lftRotate(struct Node *x)
{
struct Node *y = x->rgt;
struct Node *T2 = y->lft;
y->lft = x;
x->rgt = T2;
x->height = max(height(x->lft), height(x->rgt))+1;
y->height = max(height(y->lft), height(y->rgt))+1;
return y;
}
int getBalance(struct Node *N)
{
if (N == NULL)
return 0;
return height(N->lft) - height(N->rgt);
}
struct Node* insert(struct Node* node, int key)
{
if (node == NULL)
return(newNode(key));
if (key < node->key)
node->lft = insert(node->lft, key);
else if (key > node->key)
node->rgt = insert(node->rgt, key);
else
return node;
node->height = 1 + max(height(node->lft),
height(node->rgt));
int balance = getBalance(node);
if (balance > 1 && key < node->lft->key)
return rgtRotate(node);
if (balance < -1 && key > node->rgt->key)
return lftRotate(node);
if (balance > 1 && key > node->lft->key)
{
node->lft = lftRotate(node->lft);
return rgtRotate(node);
}
if (balance < -1 && key < node->rgt->key)
{
node->rgt = rgtRotate(node->rgt);
return lftRotate(node);
}
return node;
}
struct Node * minValueNode(struct Node* node)
{
struct Node* current = node;
/* loop down to find the lftmost leaf */
while (current->lft != NULL)
current = current->lft;
return current;
}
struct Node* deleteNode(struct Node* base, int key)
{
if (base == NULL)
return base;
if ( key < base->key )
base->lft = deleteNode(base->lft, key);
else if( key > base->key )
base->rgt = deleteNode(base->rgt, key);
else
{
if( (base->lft == NULL) || (base->rgt == NULL) )
{
struct Node *temp = base->lft ? base->lft :
base->rgt;
if (temp == NULL)
{
temp = base;
base = NULL;
}
else
*base = *temp;
free(temp);
}
else
{
struct Node* temp = minValueNode(base->rgt);
base->key = temp->key;
base->rgt = deleteNode(base->rgt, temp->key);
}
}
if (base == NULL)
return base;
base->height = 1 + max(height(base->lft),
height(base->rgt));
int balance = getBalance(base);
if (balance > 1 && getBalance(base->lft) >= 0)
return rgtRotate(base);
if (balance > 1 && getBalance(base->lft) < 0)
{
base->lft = lftRotate(base->lft);
return rgtRotate(base);
}
if (balance < -1 && getBalance(base->rgt) <= 0)
return lftRotate(base);
if (balance < -1 && getBalance(base->rgt) > 0)
{
base->rgt = rgtRotate(base->rgt);
return lftRotate(base);
}
return base;
}
void preOrder(struct Node *base)
{
if(base != NULL)
{
printf("%d ", base->key);
preOrder(base->lft);
preOrder(base->rgt);
}
}
int main()
{
struct Node *base = NULL;
base = insert(base, 27);
base = insert(base, 9);
base = insert(base, 19);
base = insert(base, 91);
base = insert(base, 90);
base = insert(base, 72);
printf("The output of an AVL tree in preOrder form: \n");
preOrder(base);
printf("\n");
base = deleteNode(base, 9);
base = deleteNode(base, 72);
printf("The tree in preOrder traversal outputs after deletion: \n");
preOrder(base);
printf("\n");
base = insert(base, 1);
base = insert(base, 2709);
printf("The tree in preOrder traversal outputs 2 more inserts: \n");
preOrder(base);
printf("\n");
return 0;
}Output:
Conclusion
In this article, we have looked into operations that make a BST balanced. In the example shown, we added extra elements in the algorithm of BST to make an AVL tree. The operations such as left rotation and right rotation along with the function to know the balance of the tree (through a height determining function), is what makes the code of an AVL tree.
Recommended Articles
This is a guide to AVL tree C program. Here we discuss How AVL tree works in the C program along with the examples and outputs. You may also have a look at the following articles to learn more –
