Want to strengthen your DSA concepts with practical examples and real-time projects?
Check out the latest Uncodemy blog and explore their DSA courses for deeper learning.
What is the Full Form of AVL Tree?
Let’s start with the basics. AVL Tree stands for Adelson-Velsky and Landis Tree, named after its inventors Georgy Adelson-Velsky and Evgenii Landis, who introduced it in 1962.
It was the first self-balancing binary search tree in computer science history.
Why Do We Need AVL Trees?
In a standard Binary Search Tree (BST), if you insert nodes in a sorted manner (ascending or descending), the tree becomes skewed essentially turning into a linked list. This drastically impacts search efficiency.
AVL Trees prevent this problem by keeping the height of the tree balanced at all times.
Properties of AVL Tree
- It is a Binary Search Tree (BST), so the left child is smaller, right child is larger.
- The difference in height between the left and right subtree (called Balance Factor) should be -1, 0, or 1 for every node.
- If the balance factor goes beyond these values, the tree performs rotations to rebalance.
What is the Balance Factor?
The balance factor of a node in an AVL tree is defined as:
Balance Factor = Height of Left Subtree - Height of Right Subtree
- If balance factor = 0 → perfectly balanced
- If balance factor = 1 or -1 → still okay
- If balance factor > 1 or < -1 → needs rotation
Types of Rotations in AVL Tree
To fix an imbalance, AVL trees use four types of rotations:
1. Left Rotation (LL Case)
2. Right Rotation (RR Case)
3. Left-Right Rotation (LR Case)
4. Right-Left Rotation (RL Case)
Example: Left Rotation (Right-Heavy Tree)
If a new node is inserted into the right subtree of a node's right child, we perform a left rotation.
C Program to Implement AVL Tree Insertion
Here’s a simplified AVL Tree implementation in C that includes insertion and balancing logic:
Copy Code
#include <stdio.h>
#include <stdlib.h>
struct Node {
int key;
struct Node *left;
struct Node *right;
int height;
};// Function to get height of tree
Copy Code
int height(struct Node *N) {
if (N == NULL)
return 0;
return N->height;
}// Get max of two integers
Copy Code
int max(int a, int b) {
return (a > b)? a : b;
}// Create new node
Copy Code
struct Node* newNode(int key) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
return(node);
}// Right rotate subtree rooted with y
Copy Code
struct Node *rightRotate(struct Node *y) {
struct Node *x = y->left;
struct Node *T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right))+1;
x->height = max(height(x->left), height(x->right))+1;
return x;
}// Left rotate subtree rooted with x
Copy Code
struct Node *leftRotate(struct Node *x) {
struct Node *y = x->right;
struct Node *T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;
return y;
}// Get balance factor
Copy Code
int getBalance(struct Node *N) {
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}// Insert into AVL Tree
Copy Code
struct Node* insert(struct Node* node, int key) {
if (node == NULL)
return(newNode(key));
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else
return node;
node->height = 1 + max(height(node->left), height(node->right));
int balance = getBalance(node);
if (balance > 1 && key < node->left->key)
return rightRotate(node);
if (balance < -1 && key > node->right->key)
return leftRotate(node);
if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}// Inorder traversal
Copy Code
void inorder(struct Node *root) {
if(root != NULL) {
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}
int main() {
struct Node *root = NULL;
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 10);
printf("Inorder traversal of AVL Tree: ");
inorder(root);
return 0;
}Output
Inorder traversal of AVL Tree: 10 20 30 40
Advantages of AVL Trees
- Ensures O(log n) time complexity for search, insert, and delete.
- Maintains strict balance, making it faster than unbalanced BSTs in most scenarios.
- Ideal for applications where frequent insertions and deletions happen.
Drawbacks
- Slightly more complex to implement due to rebalancing.
- Requires additional memory to store height/balance factor.
Use Cases of AVL Trees
- Database indexing
- File systems
- Memory management
- Network routers (routing tables)
Frequently Asked Questions (FAQs)
Q1. What is the full form of AVL Tree?
Adelson-Velsky and Landis Tree, named after the inventors.
Q2. What is the difference between AVL and BST?
AVL Tree is a self-balancing version of BST that ensures logarithmic height.
Q3. What happens when an AVL Tree becomes unbalanced?
It performs one of four rotations to regain balance: LL, RR, LR, RL.
Q4. Which is better: AVL or Red-Black Tree?
AVL provides better lookup performance but is more complex. Red-Black Trees are easier to implement in real-time systems.
Q5. Can AVL Tree have duplicate values?
Typically, no. AVL Tree is a type of BST, and BSTs don't allow duplicates.
Conclusion
The AVL Tree is a foundational concept in balancing binary search trees. With its self-adjusting structure and guaranteed log-time performance, it's an essential topic in both academic exams and tech interviews.
Want to build a strong grasp on such topics with real-world problem-solving skills?
VisitUncodemy's DSA course to master tree structures, algorithms, and beyond with hands-on learning.
