An AVL Tree is a self-balancing binary search tree (BST) where the difference between the heights of the left and right subtrees of any node (the balance factor) is at most 1. It ensures that operations like search, insertion, and deletion take O(logn)O(\log n)O(logn) time.
The AVL tree is named after its inventors, Adelson-Velsky and Landis.
Key Properties of AVL Tree
- Binary Search Tree Property:
- For any node, all keys in the left subtree are smaller, and all keys in the right subtree are larger.
- Balance Factor:
- Balance Factor=Height of Left Subtree−Height of Right Subtree\text{Balance Factor} = \text{Height of Left Subtree} – \text{Height of Right Subtree}Balance Factor=Height of Left Subtree−Height of Right Subtree
- The balance factor of any node must be −1,0,or 1-1, 0, \text{or } 1−1,0,or 1.
- Height Balancing:
- After every insertion or deletion, the tree adjusts itself using rotations to maintain the balance factor.
Rotations in AVL Tree
When a node becomes unbalanced due to an operation, one of the following rotations is applied:
- Left Rotation (LL Rotation): Applied when there’s an imbalance in the left subtree.
- Right Rotation (RR Rotation): Applied when there’s an imbalance in the right subtree.
- Left-Right Rotation (LR Rotation): Applied when there’s a left-right imbalance.
- Right-Left Rotation (RL Rotation): Applied when there’s a right-left imbalance.
Node Structure in C
struct Node {
int data;
struct Node* left;
struct Node* right;
int height; // Height of the node
};
Key Operations
1. Height of a Node
int height(struct Node* node) {
return (node == NULL) ? 0 : node->height;
}
2. Balance Factor
int getBalanceFactor(struct Node* node) {
if (node == NULL) return 0;
return height(node->left) – height(node->right);
}
Rotations
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 = 1 + max(height(x->left), height(x->right));
y->height = 1 + max(height(y->left), height(y->right));
return y;
}
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 = 1 + max(height(y->left), height(y->right));
x->height = 1 + max(height(x->left), height(x->right));
return x;
}
Left-Right Rotation
struct Node* leftRightRotate(struct Node* node) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
Right-Left Rotation
struct Node* rightLeftRotate(struct Node* node) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
Insertion in AVL Tree
To insert a node, follow these steps:
- Perform a regular BST insertion.
- Update the height of the current node.
- Check the balance factor of the node.
- Perform rotations if the node becomes unbalanced.
C Code:
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* left;
struct Node* right;
int height;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
newNode->height = 1; // New node is initially added at height 1
return newNode;
}
// Get the height of a node
int height(struct Node* node) {
return (node == NULL) ? 0 : node->height;
}
// Get the balance factor
int getBalanceFactor(struct Node* node) {
return (node == NULL) ? 0 : height(node->left) – height(node->right);
}
// 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 = 1 + max(height(y->left), height(y->right));
x->height = 1 + max(height(x->left), height(x->right));
return x;
}
// 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 = 1 + max(height(x->left), height(x->right));
y->height = 1 + max(height(y->left), height(y->right));
return y;
}
// Insert a node into 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 not allowed
}
// Update the height of the ancestor node
root->height = 1 + max(height(root->left), height(root->right));
// Get the balance factor
int balance = getBalanceFactor(root);
// If the node becomes unbalanced, perform rotations
// Left-Left (LL) Case
if (balance > 1 && data < root->left->data) {
return rightRotate(root);
}
// Right-Right (RR) Case
if (balance < -1 && data > root->right->data) {
return leftRotate(root);
}
// Left-Right (LR) Case
if (balance > 1 && data > root->left->data) {
root->left = leftRotate(root->left);
return rightRotate(root);
}
// Right-Left (RL) Case
if (balance < -1 && data < root->right->data) {
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
// Inorder traversal
void inorderTraversal(struct Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf(“%d “, root->data);
inorderTraversal(root->right);
}
}
// Main function
int main() {
struct Node* root = NULL;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
printf(“Inorder traversal of the AVL tree:\n”);
inorderTraversal(root);
return 0;
}
Output
For the input sequence 10,20,30,40,50,2510, 20, 30, 40, 50, 2510,20,30,40,50,25, the AVL tree performs rotations to balance itself. The inorder traversal will output:
10 20 25 30 40 50
Advantages of AVL Tree
- Ensures O(logn)O(\log n)O(logn) time complexity for search, insertion, and deletion.
- Self-balancing ensures optimal performance.
Disadvantages
- Requires extra storage for maintaining the height of nodes.
- Rotations increase the complexity of insert and delete operations.