AVL trees, named after their inventors Adelson-Velsky and Landis in the year 1962, are self-balancing binary search trees. In AVL trees, the balance factor and rotations are crucial for maintaining the tree's balanced structure, which ensures efficient operations.
In an AVL tree, the heights of the two child subtrees of any node differ by no more than one. If at any time they differ by more than one, rebalancing is done to restore this property.
The balance factor of a node in an AVL tree is defined as the difference in height between its left and right subtrees. Mathematically, it's calculated as:
Balance FactorBalance Factor = Height of Left Subtree − Height of Right Subtree
For an AVL tree to be balanced, the balance factor of every node must be -1, 0, or 1. Here's what these values signify:
If the balance factor of any node falls outside this range (-1, 0, 1), it indicates that the tree is unbalanced at that node, and a rotation (or series of rotations) is required to bring it back into balance.
Rotations are operations that restructure the tree in order to restore its balance. There are four types of rotations used in AVL trees:
Insertion in an AVL tree is similar to insertion in a regular binary search tree (BST), with the additional step of balancing the tree.
Deletion in an AVL tree is more complex due to the need to maintain the tree's balance.
Searching in an AVL tree is identical to searching in a regular BST, as the AVL tree maintains the BST property.
// AVL Tree operations in C
#include <stdio.h>
#include <stdlib.h>
// Structure for a node in the AVL tree
struct Node {
int data;
struct Node* left;
struct Node* right;
int height; // Height of the node
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation error\n");
exit(1);
}
newNode->data = data;
newNode->left = newNode->right = NULL;
newNode->height = 1; // Initialize height as 1 for a new node
return newNode;
}
// Function to calculate the height of a node
int getHeight(struct Node* node) {
if (node == NULL)
return 0;
return node->height;
}
// Function to find the maximum of two integers
int max(int a, int b) {
return (a > b) ? a : b;
}
// Function to perform right rotation
struct Node* rightRotate(struct Node* y) {
struct Node* x = y->left;
struct Node* T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
return x;
}
// Function to perform left rotation
struct Node* leftRotate(struct Node* x) {
struct Node* y = x->right;
struct Node* T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
return y;
}
// Function to get the balance factor of a node
int getBalanceFactor(struct Node* node) {
if (node == NULL)
return 0;
return getHeight(node->left) - getHeight(node->right);
}
// Function to insert a node into the AVL tree
struct Node* insert(struct Node* root, int data) {
if (root == NULL)
return createNode(data);
if (data < root->data)
root->left = insert(root->left, data);
else if (data > root->data)
root->right = insert(root->right, data);
else
return root; // Duplicate keys are not allowed
// Update height of current node
root->height = 1 + max(getHeight(root->left), getHeight(root->right));
// Get the balance factor to check if rotation is needed
int balance = getBalanceFactor(root);
// Left-Left case (LL)
if (balance > 1 && data < root->left->data)
return rightRotate(root);
// Right-Right case (RR)
if (balance < -1 && data > root->right->data)
return leftRotate(root);
// Left-Right case (LR)
if (balance > 1 && data > root->left->data) {
root->left = leftRotate(root->left);
return rightRotate(root);
}
// Right-Left case (RL)
if (balance < -1 && data < root->right->data) {
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
// Function to find the node with the minimum value in the tree
struct Node* findMinValueNode(struct Node* node) {
struct Node* current = node;
while (current->left != NULL)
current = current->left;
return current;
}
// Function to delete a node from the AVL tree
struct Node* deleteNode(struct Node* root, int data) {
if (root == NULL)
return root;
if (data < root->data)
root->left = deleteNode(root->left, data);
else if (data > root->data)
root->right = deleteNode(root->right, data);
else {
// Node with only one child or no child
if ((root->left == NULL) || (root->right == NULL)) {
struct Node* temp = root->left ? root->left : root->right;
// No child case
if (temp == NULL) {
temp = root;
root = NULL;
} else // One child case
*root = *temp; // Copy the contents of the non-empty child
free(temp);
} else {
// Node with two children: Get the inorder successor (smallest
// in the right subtree)
struct Node* temp = findMinValueNode(root->right);
// Copy the inorder successor's data to this node
root->data = temp->data;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->data);
}
}
// If the tree had only one node then return
if (root == NULL)
return root;
// Update height of current node
root->height = 1 + max(getHeight(root->left), getHeight(root->right));
// Get the balance factor to check if rotation is needed
int balance = getBalanceFactor(root);
// Left-Left case (LL)
if (balance > 1 && getBalanceFactor(root->left) >= 0)
return rightRotate(root);
// Left-Right case (LR)
if (balance > 1 && getBalanceFactor(root->left) < 0) {
root->left = leftRotate(root->left);
return rightRotate(root);
}
// Right-Right case (RR)
if (balance < -1 && getBalanceFactor(root->right) <= 0)
return leftRotate(root);
// Right-Left case (RL)
if (balance < -1 && getBalanceFactor(root->right) > 0) {
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
// Function for in-order traversal of the AVL tree
void inOrderTraversal(struct Node* root) {
if (root == NULL)
return;
struct Node* stack[100]; // Stack to store nodes
int top = -1; // Stack pointer
struct Node* current = root;
while (current != NULL || top >= 0) {
while (current != NULL) {
stack[++top] = current;
current = current->left;
}
current = stack[top--];
printf("%d ", current->data);
current = current->right;
}
}
// Function to free memory by deallocating nodes
void freeMemory(struct Node* root) {
if (root == NULL)
return;
freeMemory(root->left);
freeMemory(root->right);
free(root);
}
int main() {
int choice,value;
struct Node* root = NULL;
do
{
printf("1. Insertion\n2. Deletion\n3. Display\n4. Exit");
printf("\nEnter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("Enter the value to be insert: ");
scanf("%d",&value);
root = insert(root, value);
break;
case 2: printf("Enter the value to be deleted: ");
scanf("%d",&value);
root = deleteNode(root, value);
break;
case 3: inOrderTraversal(root);
break;
case 4: freeMemory(root);
break;
default: printf("\nWrong selection!!! Try again!!!");
}
}while(choice!=4);
return 0;
}